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

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

證明與費馬小定理類似

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

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

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

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

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

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

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

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

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

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


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