基本介紹
基本信息,年表,例子,其他信息,起源,偽素數謎,強偽素數,素數與偽素數通項公式,偽素數變數的充分與必要條件：,素數變數的充分與必要條件：,
基本信息
年表
1903年，馬洛（Malo）證明：若n為偽素數，則
也是一個偽素數，從而肯定了偽素數的個數是無窮的。
圖1 偽素數1950年，發現第一個偶偽素數161038=2*73*1103。
1951年，皮格（Beeger）證明了存在無限多個偶偽素數。
例子
1819年數學家薩魯斯找到了反例：
，而341=11*31是合數，341就成了第一個偽素數。以後又發現了許多偽素數：561 645 1105 1387 1729……
其他信息
起源
能整除
的合數n，a≥2，（a，n）=1，被稱為以a為底的偽素數，簡記為a-偽素數。
偽素數起源於17世紀法國數學家費馬的某些研究。他於17世紀30年代末曾寫信給法國數學家梅森，提到這樣一個命題：
能被素數p整除。後來，在他1640年10月18日給德貝西的信中說，他進一步證明了這樣一個定理：
如果p是一個素數，且a不能被p整除，則
能被P整除（等價的說法是
能被素數p整除）。
按費馬小定理，如果一個奇數n不能整除
，則n必為合數（這是費馬小定理的一個逆否命題）。但是，如果奇數n>1能整除 ， n就一定是素數嗎？就是說，費馬小定理的逆命題是否成立？對於1<n<300的數來說，計算可知，能整除 的奇數n都是素數，這使得人們在很長的時間內認為費馬小定理的逆命題當然成立。德國數學家萊布尼茨曾在1680年6月和1681年12月兩次宣布他證明了這樣一個命題：如果n不是素數，則 不能被n整除（這是下述命題的逆否命題：如果 能被n整除，則n是素數），但沒發表他的證明。1742年4月，德國數學家哥德巴赫在給歐拉的信中表示要證明費馬小定理的逆定理，但似乎也無結果。
1819年，法國數學家沙路斯發現，雖然341整除
，但341是合數，341=11×31。這一反例表明費馬小定理的逆定理不成立。1830年，一位匿名德國數學家指出更一般的構造反例的方法，他指出，只要能找到兩個奇素數p和q，使它們的積pq能同時整除
與
，那么就可得到pq整除
。按此方法，人們發現除341外，還有561，645，1105，1389，1729，1905等也具有上述性質。於是，人們把能整除 的合數n稱為偽素數。1926年，普列特製成5000萬以內的偽素數表，1938年他又推進上限到1億，為此，有時偽素數亦被稱為普列特數。
提出偽素數後自然就產生了類似素數的問題，並得到人們的研究。如偽素數有多少個？人們指出，偽素數有無窮多，1903年麥洛用一個構造性方法對此加以證明。他證明了，若n是奇偽素數，那么，
也是奇偽素數，我們已知有奇偽素數
=341，按此法就可以構造出無窮多的奇偽素數來。再如是否存在偶偽素數?1950年，美國數學家D．H．萊默爾找到了第一個偶偽素數161038，161038=2×73×1103，73 |（2161038-2），1103 |（216038-2） 。1951年，荷蘭的畢格爾又找到了一個偶偽素數，並證明了存在無窮多個偶偽素數。
後來人們針對費馬小定理的一般情況，把偽素數概念一般化，就得出前面的定義。1904年，義大利數學家奇波拉給出一種構造a-偽素數的方法：
對於已知的整數a≥2，取p是任一奇素數，使p不能整除
，則
是a-偽素數。
他同時也證明了存在無窮多的一般偽素數。當然，在一般偽素數研究中，也有許多未解決的問題。例如，1952年杜帕克提出的，能否存在無窮多個偽素數，它們同時以2和3為底，或更一般些，能否存在無窮多個偽素數，它們同時以兩個不同的整數a與b為底（a≥2，b≥2，且a與b不是同一個整數的冪）。
偽素數的一個用途是利用偽素數表來判定一個奇數n是否為素數，這是D．H．萊默爾提出來的：如果n不能整除
，則據費馬小定理知，n必為合數；如果n能整除 ，且n在偽素數表中，則n為合數，否則為素數。這種方法的關鍵就在於按偽素數表去掉偽素數，而這要求偽素數在能整除 的數中相當少才行，這就是當n整除 時，n是合數的比例問題。在前10億個自然數中，共有50847534個素數，而只有以2為底的偽素數5597個，即在此範圍內n整除 產生合數的可能性只有0.011%。所以人們把整除 的正整數n（>1）稱為殆素數。在10億之內，n整除 同時整除
的合數n只有1272個，即此時產生合數的可能性只有0.0025%。
如果存在合數n，對任何a>1，只要（a，n）=1時，n能整除
，則n被稱為卡麥可數。這種數是由美國數學家R．D．卡麥可於1912年提出來的。最小的卡麥可數為561，這種數在自然數中更少了，在10億之內，只有646個。一個問題就是：卡麥可數是否有無窮多？
偽素數謎
這個表達式無疑是數論大廈的一塊基石。對如此美妙的定理如果毫不動心，那他一定是只剩下一口氣的行屍走肉。推導這個公式用同餘式最方便，由於與素數p互素的數有p-1個，它們是：
1,2,3,...p-1
顯然有: a*2a*3a...a(p-1)=1*2*3...(p-1)（ mod p）
即: [
]*(p-1)!=(p-1)! （mod p）
因為從1到p-1之間的所有整數都於p互質，所以可以兩邊同除以(p-1)!得到：
再對a套用數學歸納法即可證明之。
但是它的逆定理是不成立的，即當 能被p整除時,p不一定是素數，在1819年，法國數學家莎路斯首先發現，雖然341能夠整除2340-1，但是341=11*31為一個合數。後來有一位德國數學家一般性地證明了，只要找到兩個奇素數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-偽素數的方法：
對於已知的整數 a>=2，取任意奇素數 p，使得 p不能整除
，則 
必是a-偽素數。比如取 a=2，選 p=5，顯然 5不能整除
，所以
是偽素數。
對於已知的整數 a>=2，由於有無窮多個奇素數不能整除a(a^2-1)，所以a-偽素數有無窮多個。
利用偽素數表,數學家D.H.萊默建議按照如下程式來判別一個奇數是否是素數：如果p不能整除
，則p必然為合數；如果p能整除，且p在偽素數表中，則p為合數，否則p為素數。顯然這是基於費馬小定理的檢驗法，我想如果再結合篩法,就會完全剔除這些偽素數。
畢竟偽素數比較稀少，在前10億個自然數中共有50847534個素數，而偽素數只有5597個，即大約只占萬分之一。而同時能以2,3為底的偽素數只有1272個，即大約5萬分之一。那么是否存在這樣的數p，它能夠整除所有的以2,3,4,...為底的費馬表達式，那么p一定是素數了吧?遺憾的是，竟然存在這樣的偽素數，它能夠整除以任何整數a為底(即使是負整數)的
,561就是最小的一個例子：
由於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)都是素數，則
(m)=(6m+1)(12m+1)(18m+1)是具有3個素因子的卡麥可數。例如取m=1，則有 (1)=7*13*19=1729是卡麥可數。類似地，自然數m是使得
(m)=(6m+1)(12m+1)(9*2m+1)...(9*2k-2m+1) (k>=4)中k個因子都是素數，則 (m)是含有k個素因子的卡麥可數。1985年，杜伯納得到了下面一些巨大的卡麥可數: m=5*7*11*13*...*397*882603*10185 時的含有3個素因子的卡麥可數(m)是一個1057位數，這是目前知道的最大的卡麥可數。其他的還有：
m=323323*655899*1040/6 時的
(m)是個207位數的卡麥可數。
m=323323*426135*1016/6 時的
(m)是個139位數的卡麥可數。
m=323323*239556*107/6 時的
(m)是個112位數的卡麥可數。
m=323323*160*8033 時的
(m)是個93位數的卡麥可數。
1978年，約里納戈發現了8個卡麥可數，它們都具有13個素數因子。這是目前所知道的含有素數因子最多的一組卡麥可數。下表是目前所知道的小於x的以2為底的偽素數個數P(x)與卡麥可數的個數C(x)的分布情況。
x P(x) C(x)
不超過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 證明了這個命題。
強偽素數
令
是三因子的Carmicheal數，定義C3，1-及C3，2-數，它們分別指
=5 mod 8,i=1,2,3及 ≡5 mod 8,i=1,2,
≡9 mod 16時的情況，它們有著較高的成為強偽素數的機率。本文首先給出成為這些數的充分必要條件然後給出算法，最後經過上機計算得到1024以內的有58個對於前5個素數基的C3,1-強偽素數，其中有一個是對於前8個素數基的強偽素數；以及27個對前4個素數基的C3,2-強偽素數，只有一個是對於前4個基的強偽素數。
素數與偽素數通項公式
偽素數變數的充分與必要條件：
1.n為奇數時：n(x,y)=3xy+x+2y,或者n(x,y)=3xy+2x+y，計算時必須滿足n(x,y)為奇數。
2.n為偶數時：n(x,y)=3xy+x+y,或者n(x,y)=3xy+2x+2y+1，計算時必須滿足n(x,y)為偶數。
滿足以上條件的n,其對應的數必為偽素數。
素數變數的充分與必要條件：
1.n為奇數時：n(x,y)≠3xy+x+2y,或者n(x,y)≠3xy+2x+y，計算時必須滿足n(x,y)為奇數。
2.n為偶數時：n(x,y)≠3xy+x+y,或者n(x,y)≠3xy+2x+2y+1，計算時必須滿足n(x,y)為偶數。
滿足以上條件的n,其對應的數必為素數。
