费马小定理

费马小定理（）是数论中的一个定理。假如是一个整数，是一个質数，那么是的倍数，可以表示为

如果不是的倍数，这个定理也可以写成更加常用的一种形式

費馬小定理的逆敘述不成立，即假如是的倍数，不一定是一个質数。例如是的倍数，但，不是質数。滿足費馬小定理的合數被稱為费马伪素数。

历史 

皮埃爾·德·費馬于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。

1736年，歐拉出版了一本名為“一些與素數有關的定理的證明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）”的論文集，其中第一次给出了證明。但從萊布尼茨未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。

有些數學家獨立提出相關的假說（有時也被錯誤地稱為中國猜想），當成立時，p是質數。這是費馬小定理的一個特殊情況。然而，這一假說的前設是錯的：例如，，而341=11×31是一個偽素數。所有的偽素數都是此假說的反例。

卡邁克爾數

如上所述，中國猜想仅有一半是正确的。符合中國猜想但不是素数的数被称为伪素数。

更极端的反例是卡迈克尔数：
假設與561互质，則被561除都余1。这样的数被称为卡邁克爾數，561是最小的卡邁克爾数。Korselt在1899年就给出了卡邁克爾數的等价定义，但直到1910年才由卡邁克爾（Robert Daniel Carmichael）发现第一个卡邁克爾数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡邁克爾数有无穷多个。

证明

方法一
（i）若是整数，是质数，且。若不能整除，则不能整除。取整數集为所有小於的正整数集合（构成的完全剩余系，即中不存在两个数同余），是中所有的元素乘以组成的集合。因为中的任何两个元素之差都不能被整除，所以中的任何两个元素之差也不能被整除。

換句話說，，考慮共個數，將它們分別除以，餘數分別為，則集合為集合的重新排列，即在餘數中恰好各出現一次；這是因為對於任兩個相異而言（），其差不是的倍數（所以不會有相同餘數），且任一個亦不為的倍數（所以餘數不為0）。因此
 
即 
 
    
在这里，且，因此将整个公式除以即得到： 
    
 
也即 
（ii）若整除，则显然有整除，即。

方法二

若为质数，为整数，且。考慮二項式係數，並限定不為或，則由於分子有質數，但分母不含，故分子的能保留，不被約分而除去，即恆為的倍數。

再考慮的二項式展開，模，則

因此

令，即得。

方法三

在抽象代数教科书中，费马小定理常作为教授拉格朗日定理时的一个简单例子。显然只需考虑  情形。此时模  所有非零的余数，在同余意义下对乘法构成一个群，这个群的阶是 。考虑群中的任何一个元素 ，根据拉格朗日定理， 的阶必整除群的阶。证毕。

應用
計算除以13的餘數

故餘數為3。

證明對於任意整數a而言，恆為2730的倍數。
易由推得，其中為正整數。
故對指數13操作如下：13減1為12，12的正因數有1, 2, 3, 4, 6, 12，分別加1，為2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13為質數，根據定理的延伸表達式，為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數，即2*3*5*7*13=2730的倍數。

推广

欧拉定理
费马小定理是欧拉定理的一个特殊情况：如果  ，那么

这里  是欧拉函数。欧拉函数的值是所有小于或等于  的正整数中与  互質的数的个数。假如  是一个素数，则  ，即费马小定理。

证明
上面证明费马小定理的群论方法，可以同理地证明欧拉定理。

考虑所有与  互素的数，这些数模  的余数所构成的集合，记为 ，并将群乘法定义为相乘后模  的同余。显然  是一个群，因为它对群乘法封闭（若  和  则 ），含幺元（即“1”），且任何一个元素  的逆元素也在集合中（因为若  则由群乘法封闭性任何 的幂次都在  中，所以  是  这个有限集的子集）。根据定义，  的阶是 ，于是根据拉格朗日定理，  中任何一个元素的阶必整除 。证毕。

卡邁克爾函數

卡邁克爾函數比欧拉函数更小。费马小定理也是它的特殊情况。

多项式除法
因為

所以由的結果可以得出的結果

用多項式除法可以得出除以的次數少於的餘式

例如，由多項式除法得到，則

這個餘式的一般結果是：

（除式）

n=0时为除式，用数学归纳法证明余式。

求

注释

参见 
费马大定理
拉格朗日定理

參考

同余
F