費馬偽質數
偽素數 / 維基百科,自由的 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 |