首先我們證明這樣一個(gè)結(jié)論：如果p是一個(gè)素?cái)?shù)的話，那么對(duì)任意一個(gè)小于p的正整數(shù)a，a, 2a, 3a, …, (p-1)a
除以p的余數(shù)正好是一個(gè)1到p-1的
排列。例如，5是素?cái)?shù)，3, 6, 9, 12除以5的余數(shù)分別為3, 1, 4, 2，正好就是1到4這四個(gè)數(shù)。
反證法，假如結(jié)論不成立的話，那么就是說有兩個(gè)小于p的正整數(shù)m和n使得na和ma除以p的余數(shù)相同。不妨假設(shè)n>m，
則p可以整除a(n-m)。但p是素
數(shù)，那么a和n-m中至少有一個(gè)含有因子p。這顯然是不可能的，因?yàn)閍和n-m都比p小。
用同余式表述，我們證明了：
(p-1)! ≡ a * 2a * 3a * … * (p-1)a (mod p)
    也即：
(p-1)! ≡ (p-1)! * a^(p-1) (mod p)
    兩邊同時(shí)除以(p-1)!，就得到了我們的最終結(jié)論：
1 ≡ a^(p-1) (mod p)

費(fèi)馬小定里的歐拉推廣：a^φ(m) ≡ 1 (mod m)（其中φ(m)為與m互質(zhì)的數(shù)的個(gè)數(shù)）

證明與費(fèi)馬小定理類似

但是費(fèi)馬小定理的逆命題并不正確，即，當(dāng)滿足a^(p-1) mod p = 1的數(shù)p不一定是素?cái)?shù)，例如p=341，a=2，
而此時(shí)p=11＊13

后來，人們又發(fā)現(xiàn)了561, 645, 1105等數(shù)都表明a=2時(shí)Fermat小定理的逆命題不成立。雖然這樣的數(shù)不多，
但不能忽視它們的存在。于是，人們把所
有能整除2^(n-1)-1的合數(shù)n叫做偽素?cái)?shù)(pseudoprime)，意思就是告訴人們這個(gè)素?cái)?shù)是假的。

不滿足2^(n-1) mod n = 1的n一定不是素?cái)?shù)；如果滿足的話則多半是素?cái)?shù)。這樣，一個(gè)比試除法效率更高的
素性判斷方法出現(xiàn)了：制作一張偽素?cái)?shù)
表，記錄某個(gè)范圍內(nèi)的所有偽素?cái)?shù)，那么所有滿足2^(n-1) mod n = 1且不在偽素?cái)?shù)表中的n就是素?cái)?shù)。之所以
這種方法更快，是因?yàn)槲覀兛梢允褂?br>二分法快速計(jì)算2^(n-1) mod n 的值，這在計(jì)算機(jī)的幫助下變得非常容易；在計(jì)算機(jī)中也可以用二分查找有序
數(shù)列、Hash表開散列、構(gòu)建Trie樹等
方法使得查找偽素?cái)?shù)表效率更高。

有人自然會(huì)關(guān)心這樣一個(gè)問題：偽素?cái)?shù)的個(gè)數(shù)到底有多少？換句話說，如果我只計(jì)算2^(n-1) mod n的值，事先
不準(zhǔn)備偽素?cái)?shù)表，那么素性判斷出
錯(cuò)的概率有多少？研究這個(gè)問題是很有價(jià)值的，畢竟我們是OIer，不可能背一個(gè)長(zhǎng)度上千的常量數(shù)組帶上考場(chǎng)。
統(tǒng)計(jì)表明，在前10億個(gè)自然數(shù)中共
有50847534個(gè)素?cái)?shù)，而滿足2^(n-1) mod n = 1的合數(shù)n有5597個(gè)。這樣算下來，算法出錯(cuò)的可能性約為0.00011。
這個(gè)概率太高了，如果想免去建
立偽素?cái)?shù)表的工作，我們需要改進(jìn)素性判斷的算法。

最簡(jiǎn)單的想法就是，我們剛才只考慮了a=2的情況。對(duì)于式子a^(n-1) mod n，取不同的a可能導(dǎo)致不同的結(jié)果。一
個(gè)合數(shù)可能在a=2時(shí)通過了測(cè)試，
但a=3時(shí)的計(jì)算結(jié)果卻排除了素?cái)?shù)的可能。于是，人們擴(kuò)展了偽素?cái)?shù)的定義，稱滿足 a^(n-1) mod n = 1的合數(shù)n叫
做以a為底的偽素?cái)?shù)(pseudoprime to base a)
。前10億個(gè)自然數(shù)中同時(shí)以2和3為底的偽素?cái)?shù)只有1272個(gè)，這個(gè)數(shù)目不到剛才的1/4。這告訴我們?nèi)绻瑫r(shí)驗(yàn)證a=2
和a=3兩種情況，算法出錯(cuò)的概率
降到了0.000025。容易想到，選擇用來測(cè)試的a越多，算法越準(zhǔn)確。通常我們的做法是，隨機(jī)選擇

若干個(gè)小于待測(cè)數(shù)的正整數(shù)作為底數(shù)a進(jìn)行若干次測(cè)試，只要有一次沒有通過測(cè)試就立即把這個(gè)數(shù)扔回合數(shù)的世界。
這就是Fermat素性測(cè)試。

人們自然會(huì)想，如果考慮了所有小于n的底數(shù) a，出錯(cuò)的概率是否就可以降到0呢？沒想到的是，居然就有這樣的合數(shù)，
它可以通過所有a的測(cè)試
（這個(gè)說法不準(zhǔn)確，詳見我在地核樓層的回復(fù)）。 Carmichael第一個(gè)發(fā)現(xiàn)這樣極端的偽素?cái)?shù)，他把它們稱作Carmichael數(shù)。
你一定會(huì)以為這樣的數(shù)一定很大。錯(cuò)。第一個(gè)Carmichael 數(shù)小得驚人，僅僅是一個(gè)三位數(shù)，561。前10億個(gè)自然數(shù)中
Carmichael數(shù)也有600個(gè)之多。Carmichael數(shù)的存在說明，我們還需要繼續(xù)加強(qiáng)素性判斷的算法。

Miller和Rabin兩個(gè)人的工作讓Fermat素性測(cè)試邁出了革命性的一步，建立了傳說中的 Miller-Rabin素性測(cè)試算法。新的測(cè)
試基于下面的定理：如果p是素?cái)?shù)，x是小于p的正整數(shù)，且x^2 mod p = 1，那么要么x=1，要么x=p-1。這是顯然的，因?yàn)?br>x^2 mod p = 1相當(dāng)于p能整除x^2-1，也即p能整除(x+1)(x-1)。由于p是素?cái)?shù)，那么只可能是x-1能被p整除(此時(shí)x=1)或x+1能
被p整除(此時(shí)x =p-1)。

這就是Miller-Rabin素性測(cè)試的方法。不斷地提取指數(shù)n-1中的因子2，把n-1表示成d*2^r（其中d是一個(gè)奇數(shù)）。那么
我們需要計(jì)算的東西就變成了a的d*2^r次方除以n的余數(shù)。于是，a^(d * 2^(r-1))要么等于1，要么等于n-1。
如果a^(d * 2^(r-1))等于1，定理繼續(xù)適用于a^(d * 2^(r-2))，這樣不斷開方開下去，直到對(duì)于某個(gè)i滿足
a^(d * 2^i) mod n = n-1或者最后指數(shù)中的2用完了得到的a^d mod n=1或n-1。這樣，F(xiàn)ermat小定理加強(qiáng)為如下形式：
盡可能提取因子 2，把n-1表示成d*2^r，如果n是一個(gè)素?cái)?shù)，那么或者a^d mod n=1，或者存在某個(gè)i使得a^(d*2^i) mod n=n-1 ( 0<=i<r ) 
（注意i可以等于0，這就把a(bǔ)^d mod n=n-1的情況統(tǒng)一到后面去了）
Miller-Rabin 素性測(cè)試同樣是不確定算法，我們把可以通過以a為底的Miller-Rabin測(cè)試的合數(shù)稱作以a為底的強(qiáng)偽素
數(shù)(strong pseudoprime)。
第一個(gè)以2為底的強(qiáng)偽素?cái)?shù)為2047。第一個(gè)以2和3為底的強(qiáng)偽素?cái)?shù)則大到1 373 653。

 Miller- Rabin算法的代碼也非常簡(jiǎn)單：計(jì)算d和r的值（可以用位運(yùn)算加速），然后二分計(jì)算a^d mod n的值
，最后把它平方r次。程序的代碼比想像中的更簡(jiǎn)單，我寫一份放在下邊。雖然我已經(jīng)轉(zhuǎn)C了，但我相信還有很多
人看不懂C語言。我再寫一次Pascal 吧。函數(shù)IsPrime返回對(duì)于特定的底數(shù)a，n是否是能通過測(cè)試。如果函數(shù)返回
False，那說明n不是素?cái)?shù)；如果函數(shù)返回True，那么n極有可能是素?cái)?shù)。注意這個(gè)代碼的數(shù)據(jù)范圍限制在longint，
你很可能需要把它們改成int64或高精度計(jì)算。
    我們下面來演示一下上面的定理如何應(yīng)用在Fermat素性測(cè)試上。前面說過341可以通過以2為底的Fermat測(cè)試，
因?yàn)?2^340 mod 341=1。如果341真是素?cái)?shù)的話，那么2^170 mod 341只可能是1或340；當(dāng)算得2^170 mod 341確實(shí)等于
1時(shí)，我們可以繼續(xù)查看2^85除以341的結(jié)果。我們發(fā)現(xiàn)，2^85 mod 341=32，這一結(jié)果摘掉了341頭上的素?cái)?shù)皇冠，
面具后面真實(shí)的嘴臉顯現(xiàn)了出來


  對(duì)于大數(shù)的素性判斷，目前Miller-Rabin算法應(yīng)用最廣泛。一般底數(shù)仍然是隨機(jī)選取，但當(dāng)待測(cè)數(shù)不太大時(shí)，
選擇測(cè)試底數(shù)就有一些技巧了。比如，如果被測(cè)數(shù)小于4 759 123 141，那么只需要測(cè)試三個(gè)底數(shù)2, 7和61就足
夠了。當(dāng)然，你測(cè)試的越多，正確的范圍肯定也越大。如果你每次都用前7個(gè)素?cái)?shù)(2, 3, 5, 7, 11, 13和17)進(jìn)行
測(cè)試，所有不超過341 550 071 728 320的數(shù)都是正確的。如果選用2, 3, 7, 61和24251作為底數(shù)，那么10^16內(nèi)
唯一的強(qiáng)偽素?cái)?shù)為46 856 248 255 981。這樣的一些結(jié)論使得Miller-Rabin算法在OI中非常實(shí)用。通常認(rèn)為，Miller-Rabin素性測(cè)試
的正確率可以令人接受，隨機(jī)選取 k個(gè)底數(shù)進(jìn)行測(cè)試算法的失誤率大概為4^(-k)。