费马伪素数
偽素數 / 维基百科,自由的 encyclopedia
费马伪素数(英语:Fermat pseudoprime)是指满足费马小定理的伪素数,也是最重要的一类伪素数。
此条目没有列出任何参考或来源。 (2021年11月1日) |
其定义是:对自然数和一个与其互素的自然数a,如果整除 ax-1 - 1,则称是一个以a为底的费马伪素数或者关于a的费马伪素数。最小的费马伪素数是341(=11×31,关于2)。如果关于任何与其互素的数都是费马伪素数,则称是绝对伪素数(或卡迈克尔数,来自找到第一个绝对伪素数的数学家罗伯特·丹尼·卡迈克尔)。最小的绝对伪素数是561。
有人已经证明了费马伪素数的个数是无穷的。有一位数学家如此评论:“对于素数,费马小定理肯定是正确的;但他没说在合数中就不正确。”事实上,费马小定理给出的是关于素数判定的必要不充分条件。
另外,若:不是素数(如下表中的情况),则它就一定是伪素数。 这些当中包含了所有的费马合数(当n=2k),梅森合数(当n=p)及瓦格斯塔夫合数(当n=2p)
分圆多项式阶数n | 伪素数 |
11 | 2047=23x89 |
23 | 8388607=47x178481 |
25 | 1082401=601x1801 |
28 | 3277=29x113 |
29 | 536870911=233x1103x2089 |
35 | 8727391=71x122921 |
36 | 4033=37x109 |
37 | 137438953471=223x616318177 |
39 | 9588151=79x121369 |