費(fèi)馬小定理（英文：Fermat small theorem），簡(jiǎn)稱費(fèi)馬定理，是初等數(shù)論的重要定理。該定理表述為：若p是個(gè)素?cái)?shù)，a是不能被p整除的整數(shù)，則p整除ap-1-1。此外，從同余的角度也能對(duì)該定理進(jìn)行表述。
1637年，法國(guó)數(shù)學(xué)家皮耶·德·費(fèi)瑪（Pierre de Fermat）在閱讀古希臘數(shù)學(xué)家丟番圖（Diophantus）所著的《算術(shù)》譯本過程中，對(duì)素?cái)?shù)和整數(shù)的可除性問題進(jìn)行了研究工作，后于1640年10月18日，費(fèi)馬在一封寫給德·貝西（B.F.de Bessy）的信中給出了費(fèi)馬小定理，但并未作出相關(guān)證明。德國(guó)數(shù)學(xué)家戈特弗里德·萊布尼茨（G.W.Leibniz）在1683年未發(fā)表的一篇手稿中，給出了費(fèi)馬小定理的早期證明。1736年，瑞士數(shù)學(xué)家萊昂哈德·歐拉（L.Euler）正式發(fā)表了費(fèi)馬小定理的第一個(gè)證明，并于1760年對(duì)它進(jìn)行了推廣。后來，德國(guó)約翰·卡爾·弗里德里希·高斯（C.F.Gauss）在1801年發(fā)表的著作《算術(shù)研究》一書中，給出了同余的符號(hào)，并用同余式簡(jiǎn)捷地證明了費(fèi)馬小定理。在東方，中國(guó)清代數(shù)學(xué)家李善蘭在1872年著成的《考數(shù)根法》一書中也證明了費(fèi)馬小定理，并指出它的逆命題不真。20世紀(jì)，費(fèi)馬小定理出現(xiàn)在亨塞爾（K.Hensel）的書中，與有限群有關(guān)。
費(fèi)馬小定理可由多種方法證明，如數(shù)學(xué)歸納法、歐拉定理證法、周期點(diǎn)證法。由費(fèi)馬小定理可得出偽素?cái)?shù)的概念，它還可用于判斷數(shù)的整除性和求解不定方程。此外，費(fèi)馬小定理在現(xiàn)實(shí)世界中具有廣泛的應(yīng)用價(jià)值，如密碼學(xué)中，RSA公開密鑰算法的基礎(chǔ)理論就是依據(jù)數(shù)論中的費(fèi)馬小定理來對(duì)大數(shù)進(jìn)行質(zhì)因數(shù)分解。
定理內(nèi)容
費(fèi)馬小定理：若是個(gè)素?cái)?shù)，為整數(shù)，若，則整除。
同余角度的解釋：設(shè)為素?cái)?shù)，為整數(shù)，若，則，或在同余號(hào)兩邊同乘，可得。
簡(jiǎn)史
早期起源
數(shù)論有著悠久的發(fā)展歷史，早在公元前3世紀(jì)的古希臘時(shí)代，數(shù)學(xué)家歐幾里得（Euclid）所著《幾何原本》一書中就記載了對(duì)素?cái)?shù)無限性的證明、整數(shù)的因數(shù)分解、求兩個(gè)正整數(shù)最大公因數(shù)的輾轉(zhuǎn)相除法等相關(guān)理論。1637年，法國(guó)數(shù)學(xué)家皮耶·德·費(fèi)瑪（Pierre de Fermat）在閱讀古希臘數(shù)學(xué)家丟番圖（Diophantus）所著的《算術(shù)》譯本過程中對(duì)于素?cái)?shù)和整數(shù)的可除性問題給出了許多論斷。后來，1640年10月18日，費(fèi)馬在一封寫給德·貝西（B.F.de Bessy）的信中給出了費(fèi)馬小定理：若是個(gè)素?cái)?shù)而與互質(zhì)，則能為整除。但費(fèi)馬并未作出相關(guān)證明。
后續(xù)發(fā)展
早在1683年，德國(guó)數(shù)學(xué)家戈特弗里德·萊布尼茨（G.W.Leibniz）未發(fā)表的一篇手稿中記載了關(guān)于費(fèi)馬小定理的一個(gè)證明。后來，瑞士數(shù)學(xué)家萊昂哈德·歐拉（L.Euler）在1736年正式發(fā)表了關(guān)于費(fèi)馬小定理的第一個(gè)證明，并于1760年引進(jìn)了歐拉函數(shù)，推廣了費(fèi)馬小定理：如果與互素，則可以被整除。該定理被稱為歐拉定理，費(fèi)馬小定理是它的一個(gè)特例。1801年，德國(guó)約翰·卡爾·弗里德里希·高斯（C.F.Gauss）在發(fā)表的著作《算術(shù)研究》一書中，定義了有理整數(shù)模一個(gè)自然數(shù)同余的概念，給出了同余的符號(hào)，并用同余式簡(jiǎn)捷地證明了費(fèi)馬小定理。在東方，中國(guó)清代數(shù)學(xué)家李善蘭在1872年著成的《考數(shù)根法》中也證明了費(fèi)馬小定理，并指出它的逆命題不真。此外，在1913年德國(guó)數(shù)學(xué)家亨塞爾（K.Hensel）出版的著作《數(shù)論》一書中，費(fèi)馬小定理還與有限群相關(guān)。
幾何意義
如圖1，當(dāng)時(shí)，費(fèi)馬小定理的幾何意義為：為素?cái)?shù)時(shí)，函數(shù)與的圖形的個(gè)交點(diǎn)中含與圖形的個(gè)交點(diǎn)，交點(diǎn)個(gè)數(shù)之差是的整數(shù)倍。
證明
數(shù)學(xué)歸納法
證明：對(duì)用數(shù)學(xué)歸納法，時(shí)顯然成立，設(shè)成立，考察，是整數(shù)，是的倍數(shù)（分子的不可能被分母消去，因），故，證畢。
歐拉定理證法
證明：設(shè)是歐拉函數(shù)，于是，由于是一個(gè)素?cái)?shù)，所以，又，故。那么，在歐拉定理中，取，就有，證畢。
周期點(diǎn)證法
證明：考慮在度量空間上，根據(jù)移位映射與不動(dòng)點(diǎn)的定義可知有個(gè)點(diǎn)滿足，其中有個(gè)是的不動(dòng)點(diǎn)。而是素?cái)?shù)，故這個(gè)點(diǎn)中除有個(gè)不動(dòng)點(diǎn)外沒有其他周期小于的周期點(diǎn)，即是素?cái)?shù)時(shí)，有個(gè)周期點(diǎn)，它們構(gòu)成條周期軌，所以為一整數(shù)，證畢。
衍生概念
偽素?cái)?shù)
通常，費(fèi)馬小定理的逆定理不一定成立，即時(shí)，不一定是素?cái)?shù)。但對(duì)于特殊情形，逆定理是可成立的。
定理：若，且對(duì)于的任一真因數(shù)，有，則是素?cái)?shù)，被稱為偽素?cái)?shù)。
偽素?cái)?shù)：一般地，把滿足的合數(shù)稱為偽素?cái)?shù)。
絕對(duì)偽素?cái)?shù)：如果為合數(shù)且對(duì)任何與互質(zhì)的整數(shù)都有，則稱為絕對(duì)偽素?cái)?shù)（或者卡邁克爾偽素?cái)?shù)）。
例如，是一個(gè)偽素?cái)?shù)，但不是絕對(duì)偽素?cái)?shù)；是最小的絕對(duì)偽素?cái)?shù)。
相關(guān)算法
米勒-拉賓素性檢驗(yàn)
米勒-拉賓算法是基于概率的素?cái)?shù)測(cè)試算法，它的理論基礎(chǔ)是費(fèi)馬小定理，可表述為：如果是一個(gè)奇素?cái)?shù)，將表示成的形式（是奇數(shù)），是和互素的任何整數(shù)，那么或者對(duì)某個(gè)等式成立。
方法
設(shè)待檢測(cè)的整數(shù)為，米勒-拉賓算法包括如下步驟：
（1) 計(jì)算整除的次數(shù)（即是能整除的的最大冪），然后計(jì)算，使得；
（2）選擇一個(gè)小于的隨機(jī)數(shù)；
（3）設(shè)，計(jì)算；
（4）如果或，那么通過測(cè)試，可能是素?cái)?shù)；
（5）如果且，那么是合數(shù)；
（6）令，如果且，設(shè)，然后返回到（5），如果，那么通過測(cè)試，可能是素?cái)?shù)；
（7）如果且，那么為合數(shù)。
推廣
周期點(diǎn)數(shù)計(jì)數(shù)公式
周期點(diǎn)定義：如果，則稱為的一個(gè)階周期點(diǎn)，與這個(gè)點(diǎn)的集合稱為的一個(gè)階軌道。
用表示有限集合的元素個(gè)數(shù)，則有：設(shè)是的素?cái)?shù)冪分解式，若的階周期點(diǎn)的個(gè)數(shù)有限，則
。
推廣：設(shè)是的素?cái)?shù)冪分解式，則對(duì)任何自然數(shù)，
有，
當(dāng)為素?cái)?shù)時(shí)，，那么式為，即是費(fèi)馬小定理的歐拉形式。
進(jìn)一步地，在時(shí)，則有充分必要。換言之，若，則，其中，則皮耶·德·費(fèi)瑪歐拉定理成立。
應(yīng)用例題
判斷數(shù)的整除性
例題 證明可被整除。
證明：應(yīng)用費(fèi)馬小定理有：
，
，因不是素?cái)?shù)，應(yīng)用二項(xiàng)式系數(shù)，有
（1）由首尾等距結(jié)合分組，共分組，可證明有因子。
（2），將單獨(dú)計(jì)算，再二次分組，采用首尾結(jié)合，可證明中必有因子。
（3），一次分組，除過后，二次分組，首尾結(jié)合各數(shù)可證明必含因子。
（4）偶數(shù)的次方必可被除盡，其余奇數(shù)項(xiàng)共有項(xiàng)。個(gè)奇數(shù)次冪之和必然可被整除。與各偶數(shù)次冪的和必可被整除。
（5）除過外，首尾結(jié)合與與與與其次冪應(yīng)用公式可證得中必有因子，從而證畢。
求解不定方程
例題 求證：有的解時(shí)，中必有一成立。
證明：假設(shè)，則。
所以，。
則，與已知條件矛盾，即原命題成立。
應(yīng)用
密碼學(xué)
高級(jí)加密標(biāo)準(zhǔn)
在高級(jí)加密標(biāo)準(zhǔn)中，盒算法是一個(gè)非線性的字節(jié)代替變換，是整個(gè)高級(jí)加密標(biāo)準(zhǔn)加解密硬件實(shí)現(xiàn)的關(guān)鍵模塊。基于費(fèi)馬小定理的正逆盒算法原理及運(yùn)算特點(diǎn)，可設(shè)計(jì)一種小規(guī)模、快速的可逆盒運(yùn)算電路，它能實(shí)現(xiàn)盒的正逆運(yùn)算，加速盒運(yùn)算的過程，并且有效減小解密電路的規(guī)模，對(duì)高級(jí)加密標(biāo)準(zhǔn)算法的硬件實(shí)現(xiàn)具有實(shí)際價(jià)值。
公鑰密碼算法
在密碼學(xué)中，信息安全是一個(gè)重要的研究領(lǐng)域。公鑰密碼經(jīng)常會(huì)用到大素?cái)?shù)，而較好的素性檢驗(yàn)算法通常都是基于費(fèi)馬小定理，它給出了數(shù)的素性檢驗(yàn)的必要條件，因此被廣泛應(yīng)用于密碼學(xué)。例如，RSA公開密鑰算法，它的基礎(chǔ)理論就是依據(jù)數(shù)論中費(fèi)馬小定理來對(duì)大數(shù)進(jìn)行質(zhì)因數(shù)分解。
參考資料 >