標籤:卡邁克爾數

偽素數,又叫做偽質數:它滿足費馬小定理,但其本身卻不是素數。最小的偽素數是341。有人已經證明了偽素數的個數是無窮的。事實上,費馬小定理給出的是關於素數判定的必要非充分條件。若n能整除2^(n-1)-1,並n是非偶數的合數,那麼n就是偽素數。第一個偽素數341 是薩魯斯(Sarrus)在1819年發現的。

1基本信息

偽素數的例子
2^(5-1)-1=15,15|5. 2^(3-1)-1=3,3|3.但很多都是素數,如3,5,7,29,31……
1819年數學家薩魯斯找到了反例:2^(341-1)-1|341,而341=11*31是合數,341就成了第一個偽素數。以後又發現了許多偽素數:561 645 1105 1387 1729……

2其他信息

偽素數之謎
享有"業餘數學之王"稱號的費馬曾經證明:若p為素數,則a^p-a是p的倍數,進一步如果p與a互素,則顯然a^(p-1)-1是p的倍數,用同餘式來表達就是:
a^(p-1)=1 (mod p)
這個表達式無疑是數論大廈的一塊基石.對如此美妙的定理如果毫不動心,那他一定是只剩下一口氣的行屍走肉.推導這個公式用同餘式最方便,由於與素數p互素的數有p-1個,它們是:
1,2,3,...p-1
顯然有: a*2a*3a...a(p-1)=1*2*3...(p-1)( mod p)
即: [a^(p-1)]*(p-1)!=(p-1)! (mod p)
因為從1到p-1之間的所有整數都於p互質,所以可以兩邊同除以(p-1)!得到:
a^(p-1)=1 (mod p)
再對a應用數學歸納法即可證明之.
但是它的逆定理是不成立的,即當a^(p-1)-1能被p整除時,p不一定是素數,在1819年,法國數學家莎路斯首先發現,雖然341能夠整除2340-1,但是341=11*31為一個合數.後來有一位德國數學家一般性地證明了,只要找到兩個奇素數p,q,使得它們的積能同時整除2^(p-1)-1,與2^(q-1)-1,就能保證pq整除2^(pq-1)-1.
偽素數有無窮多個,第一個證明這一點的是數學家邁羅在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-偽素數的方法:
對於已知的整數 a>=2,取任意奇素數 p,使得 p不能整除a(a2-1),則 n=(a2p-1)/(a2-1)必是a-偽素數.比如取 a=2,選 p=5,顯然 5不能整除2(22-1)=6,所以(210-1)/(22-1)=341 是偽素數.
對於已知的整數 a>=2,由於有無窮多個奇素數不能整除a(a2-1),所以a-偽素數有無窮多個.
利用偽素數表,數學家D.H.萊默建議按照如下程序來判別一個奇數是否是素數:如果p不能整除2p-1-1,則p必然為合數;如果p能整除2p-1-1,且p在偽素數表中,則p為合數,否則p為素數.顯然這是基於費馬小定理的檢驗法,我想如果再結合篩法,就會完全剔除這些偽素數.
畢竟偽素數比較稀少,在前10億個自然數中共有50847534個素數,而偽素數只有5597個,即大約只佔萬分之一.而同時能以2,3為底的偽素數只有1272個,即大約5萬分之一.那麼是否存在這樣的數p,它能夠整除所有的以2,3,4,...為底的費馬錶達式,那麼p一定是素數了吧?遺憾的是,竟然存在這樣的偽素數,它能夠整除以任何整數a為底(即使是負整數)的ap-1-1,561就是最小的一個例子:
a560-1=(a2)280-1=(a2-1)(...)=(a10-1)(...)=(a16-1)(...)
由於561=3*11*17,而由費馬小定理,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為自然數,且使得(6m+1),(12m+1),(18m+1)都是素數,則M3(m)=(6m+1)(12m+1)(18m+1)是具有3個素因子的卡邁克爾數.例如取m=1,則有M3(1)=7*13*19=1729是卡邁克爾數.類似地,自然數m是使得
Mk(m)=(6m+1)(12m+1)(9*2m+1)...(9*2k-2m+1) (k>=4)
中k個因子都是素數,則Mk(m)是含有k個素因子的卡邁克爾數.1985年,杜伯納得到了下面一些巨大的卡邁克爾數: m=5*7*11*13*...*397*882603*10185 時的含有3個素因子的卡邁克爾數M3(m)是一個1057位數,這是目前知道的最大的卡邁克爾數.其他的還有
m=323323*655899*1040/6 時的M4(m)是個207位數的卡邁克爾數.
m=323323*426135*1016/6 時的M5(m)是個139位數的卡邁克爾數.
m=323323*239556*107/6 時的M6(m)是個112位數的卡邁克爾數.
m=323323*160*8033 時的M7(m)是個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) 卡邁克爾數是否有無窮多個?
愛多士猜想有無限個卡邁克爾數,1994年 William Alford 、 Andrew Granville 及 Carl Pomerance 證明了這個命題.

強偽素數

令N=q1q2q3,q1<q2<q3是三因子的Carmicheal數,定義C3,1-及C3,2-數,它們分別指qi=5 mod 8,i=1,2,3及qi≡5 mod 8,i=1,2,q3≡9 mod 16時的情況,它們有著較高的成為強偽素數的概率.本文首先給出成為這些數的充分必要條件然後給出演算法,最後經過上機計算得到1024以內的有58個對於前5個素數基的C3,1-強偽素數,其中有一個是對於前8個素數基的強偽素數;以及27個對前4個素數基的C3,2-強偽素數,只有一個是對於前4個基的強偽素數.

相關評論

同義詞:暫無同義詞