偽素數

若n能整除,並n是非偶數的合數，那麼n就是偽素數。

,. ,.但很多都是素數，如3，5，7，29，31……

1919年數學家薩魯斯找到了反例：,而是合數，341就成了第一個偽素數。以後又發現了許多偽素數：561 645 1105 1387 1729……

能整除的合數n，，，被稱為以a為底的偽素數，簡記為a-偽素數。

偽素數起源於17世紀法國數學家費馬的某些研究。他於17世紀30年代末曾寫信給法國數學家梅森，提到這樣一個命題：能被素數p整除。後來，在他1640年10月18日給德貝西的信中說，他進一步證明了這樣一個定理：

如果p是一個素數，且a不能被p整除，則能被P整除（等價的說法是能被素數p整除）。

後人稱這個定理為費馬小定理，以和費馬大定理相區別。費馬小定理奠定了現代數論中素數判定的基礎。

按費馬小定理，如果一個奇數n不能整除，則n必為合數（這是費馬小定理的一個逆否命題）。但是，如果奇數能整除， n就一定是素數嗎？就是說，費馬小定理的逆命題是否成立？對於的數來說，計算可知，能整除的奇數n都是素數，這使得人們在很長的時間內認為費馬小定理的逆命題當然成立。德國數學家萊布尼茨曾在1680年6月和1681年12月兩次宣布他證明了這樣一個命題：如果n不是素數，則不能被n整除（這是下述命題的逆否命題：如果能被n整除，則n是素數），但沒發表他的證明。1742年4月，德國數學家哥德巴赫在給歐拉的信中表示要證明費馬小定理的逆定理，但似乎也無結果。

1819年，法國數學家沙路斯發現，雖然341整除，但341是合數，。這一反例表明費馬小定理的逆定理不成立。1830年，一位匿名德國數學家指出更一般的構造反例的方法，他指出，只要能找到兩個奇素數p和q，使它們的積pq能同時整除與，那麼就可得到pq整除。按此方法，人們發現除341外，還有561，645，1105，1389，1729，1905等也具有上述性質。於是，人們把能整除的合數n稱為偽素數。1926年，普列特製成5000萬以內的偽素數表，1938年他又推進上限到1億，為此，有時偽素數亦被稱為普列特數。

提出偽素數后自然就產生了類似素數的問題，並得到人們的研究。如偽素數有多少個？人們指出，偽素數有無窮多，1903年麥洛用一個構造性方法對此加以證明。他證明了，若n是奇偽素數，那麼，也是奇偽素數，我們已知有奇偽素數n0＝341，按此法就可以構造出無窮多的奇偽素數來。再如是否存在偶偽素數?1950年，美國數學家D．H．萊默爾找到了第一個偶偽素數161038，，， 。1951年，荷蘭的畢格爾又找到了一個偶偽素數，並證明了存在無窮多個偶偽素數。

後來人們針對費馬小定理的一般情況，把偽素數概念一般化，就得出前面的定義。1904年，義大利數學家奇波拉給出一種構造a-偽素數的方法：

對於已知的整數，取p是任一奇素數，使p不能整除，則是a-偽素數。

他同時也證明了存在無窮多的一般偽素數。當然，在一般偽素數研究中，也有許多未解決的問題。例如，1952年杜帕克提出的，能否存在無窮多個偽素數，它們同時以2和3為底，或更一般些，能否存在無窮多個偽素數，它們同時以兩個不同的整數a與b為底（，，且a與b不是同一個整數的冪）。

偽素數的一個用途是利用偽素數表來判定一個奇數n是否為素數，這是D．H．萊默爾提出來的：如果n不能整除，則據費馬小定理知，n必為合數；如果n能整除，且n在偽素數表中，則n為合數，否則為素數。這種方法的關鍵就在於按偽素數表去掉偽素數，而這要求偽素數在能整除的數中相當少才行，這就是當n整除時，n是合數的比例問題。在前10億個自然數中，共有50847534個素數，而只有以2為底的偽素數5597個，即在此範圍內n整除產生合數的可能性只有。所以人們把整除的正整數稱為殆素數。在10億之內，n整除同時整除的合數n只有1272個，即此時產生合數的可能性只有。

如果存在合數n，對任何，只要時，n能整除，則n被稱為卡邁克爾數。這種數是由美國數學家R．D．卡邁克爾於1912年提出來的。最小的卡邁克爾數為561，這種數在自然數中更少了，在10億之內，只有646個。一個問題就是：卡邁克爾數是否有無窮多？

享有"業餘數學之王"稱號的費馬曾經證明：若p為素數，則是p的倍數，進一步如果p與a互素，則顯然是p的倍數，用同餘式來表達就是:

這個表達式無疑是數論大廈的一塊基石。對如此美妙的定理如果毫不動心，那他一定是只剩下一口氣的行屍走肉。推導這個公式用同餘式最方便，由於與素數p互素的數有p-1個，它們是:

1,2,3,...p-1

顯然有:

即:

兩邊同除以得到:

再對a應用數學歸納法即可證明之.

但是它的逆定理是不成立的，即當能被p整除時,p不一定是素數，在1819年，法國數學家莎路斯首先發現，雖然341能夠整除2340-1,但是為一個合數。後來有一位德國數學家一般性地證明了，只要找到兩個奇素數p,q,使得它們的積能同時整除,與,就能保證pq整除.

偽素數有無窮多個，第一個證明這一點的是數學家邁羅在1903年給出的。如果n是偽素數，則2n-1也是偽素數，所以偽素數有無窮多個。除了上述的341之外，人們陸續發現了561,645,1105,1387,1729,1905等等。數學家普列特在1938年做出了1億以內的偽素數表。因此偽素數又叫做普列特數.

除了奇偽素數以外，竟然還有偶偽素數存在，美國著名數學家D.H.萊默在1950年找到了第一個偶偽素數:161038,後來荷蘭數學家畢格爾又發現了3個偶偽素數:215326,2568226和143742226,並且從理論上證明了存在無窮多個偶偽素數.

偽素數是針對底數為2的情形提出的。而對於一般的底數a,則提出了a-偽素數的概念，例如91能整除390-1,所以把91稱為3-偽素數.1904年，義大利數學家奇波拉給出了一種構造a-偽素數的方法:

對於已知的整數 ,取任意奇素數 p,使得 p不能整除,則 必是a-偽素數。比如取 ,選,顯然 5不能整除,所以是偽素數.

對於已知的整數,由於有無窮多個奇素數不能整除所以a-偽素數有無窮多個.

利用偽素數表，數學家D.H.萊默建議按照如下程序來判別一個奇數是否是素數：如果p不能整除,則p必然為合數；如果p能整除,且p在偽素數表中，則p為合數，否則p為素數。顯然這是基於費馬小定理的檢驗法，我想如果再結合篩法，就會完全剔除這些偽素數.

畢竟偽素數比較稀少，在前10億個自然數中共有50847534個素數，而偽素數只有5597個，即大約只佔萬分之一。而同時能以2,3為底的偽素數只有1272個，即大約5萬分之一。那麼是否存在這樣的數p,它能夠整除所有的以2,3,4,...為底的費馬錶達式，那麼p一定是素數了吧？遺憾的是，竟然存在這樣的偽素數，它能夠整除以任何整數a為底(即使是負整數)的,561就是最小的一個例子:

由於,而由費馬小定理,3,11,17都能夠整除上式，所以561也能夠整除上式。這種極端的偽素數叫做絕對偽素數，又由於是首先由美國數學家卡邁克爾在1912年發現的，所以又叫做卡邁克爾數，為了判別什麼樣的整數是卡邁克爾數，他發現了一個準則:

如果整數n滿足如下條件

(1) n沒有平方因子，即n沒有相同的素因子;

(2) n是奇數且至少有3個不同的素數因子;

(3) 對於n的每一個素數因子p,p-1能夠整除n-1;

則 n 必為卡邁克爾數。反之，如果 n是卡邁克爾數，則 n必滿足上述3個條件.

1939年，數學家切尼克給出了一種構造卡邁克爾數的方法:

設m為自然數，且使得,都是素數，則是具有3個素因子的卡邁克爾數。例如取,則有是卡邁克爾數。類似地，自然數m是使得

中k個因子都是素數，則是含有k個素因子的卡邁克爾數.1985年，杜伯納得到了下面一些巨大的卡邁克爾數: 時的含有3個素因子的卡邁克爾數是一個1057位數，這是目前知道的最大的卡邁克爾數。其他的還有

時的是個207位數的卡邁克爾數.

時的是個139位數的卡邁克爾數.

時的是個112位數的卡邁克爾數.

時的是個93位數的卡邁克爾數.

1978年，約里納戈發現了8個卡邁克爾數,它們都具有13個素數因子。這是目前所知道的含有素數因子最多的一組卡邁克爾數。下表是目前所知道的小於x的以2為底的偽素數個數P(x)與卡邁克爾數的個數C(x)的分佈情況.

x P(x) C(x)

1000 8 1

10000 22 7

100000 78 16

1000000 245 43

10000000 750 105

100000000 2057 255

1000000000 5597 646

10000000000 14887 1547

不超過100000的16個卡邁克爾數如下:

561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361

留給人們的未解之謎是;

(1) 同時以a,b為底的偽素數是否有無窮多個?

(2) 卡邁克爾數是否有無窮多個?