费马小定理

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

如果不是的倍数，這個定理也可以寫成更加常用的一種形式
Fermat's Little Theorem .WolframMathWorld.

註：如果是的倍数，則

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

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

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

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

卡邁克爾數

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

更极端的反例是卡迈克尔数：
假設與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的倍數。
證明對於任意整數a而言，恆為3300的倍數。

為132的倍數。
模仿前述操作，11減1為10，10的正因數有1, 2, 5, 10，分別加1，為2, 3, 6, 11，其中2, 3, 11為質數，因此為2, 3, 11的最小公倍數的倍數，即66的倍數。
考慮，因為奇數的11次方仍為奇數，且奇數與奇數之和為偶數，故當a為奇數時，為偶數；同理可知當a為偶數時，仍為偶數。因此當a為任意整數時，為偶數。
因此的倍數的倍數的倍數。
為25的倍數。
由後文的欧拉定理可知（當a與25互質時），即（當a為任意整數時）。因此為25的倍數。
因此為132與25的的最小公倍數的倍數，即3300的倍數。

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

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

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

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

卡邁克爾函數

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

多项式除法
因為

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

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

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

這個餘式的一般結果是：

（除式）

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

求

注释

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

參考

Category:同余
F