费马小定理

Template:NoteTA 费马小定理（Template:Lang-en）是数论中的一个定理。假如$a$是一个整数，$p$是一个質数，那么$a^p-a$是$p$的倍数，可以表示为

$a^p\equiv a(\mathrm{mod}p)$

如果$a$不是$p$的倍数，這個定理也可以寫成更加常用的一種形式

$a^{p-1}\equiv 1(\mathrm{mod}p)$Template:Notetag

註：如果$a$是$p$的倍数，則

$a^{p-1}\equiv 0(\mathrm{mod}p)$

費馬小定理的逆敘述不成立，即假如$a^p-a$是$p$的倍数，$p$不一定是一个質数。例如$2^{341}-2$是$341$的倍数，但$341=11\times 31$，不是質数。滿足費馬小定理的合數被稱為费马伪素数。

历史

皮埃爾·德·費馬

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

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

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

卡邁克爾數

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

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

证明

方法一

（i）若$a$是整数，$p$是质数，且$\gcd (a,p)=1$。若$p$不能整除$x-y$，则$p$不能整除$a(x-y)$。取整數集$A$为所有小於$p$的正整数集合（$A$构成$p$的完全剩余系，即$A$中不存在两个数同余$p$），$B$是$A$中所有的元素乘以$a$组成的集合。因为$A$中的任何两个元素之差都不能被$p$整除，所以$B$中的任何两个元素之差也不能被$p$整除。

換句話說，$\gcd (a,p)=1$，考慮$1\times a,2\times a,3\times a,....(p-1)\times a$共$(p-1)$個數，將它們分別除以$p$，餘數分別為$r_1,r_2,r_3,....,r_{p-1}$，則集合$\{r_1,r_2,r_3,....,r_{p-1}\}$為集合$\{1,2,3,\dots ,(p-1)\}$的重新排列，即$1,2,3,\dots ,(p-1)$在餘數中恰好各出現一次；這是因為對於任兩個相異$k*a$而言（$k=1,2,3,\dots ,(p-1)$），其差不是$p$的倍數（所以不會有相同餘數），且任一個$k*a$亦不為$p$的倍數（所以餘數不為0）。因此

$1\cdot 2\cdot 3\cdot \dots \cdot (p-1)\equiv (1\cdot a)\cdot (2\cdot a)\cdot \dots \cdot ((p-1)\cdot a)(\mathrm{mod}p),$

即

$W\equiv W\cdot a^{p-1}(\mathrm{mod}p),$

在这里$W=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)$，且$(W,p)=1$，因此将整个公式除以$W$即得到：

$a^{p-1}\equiv 1(\mathrm{mod}p)$

也即 $a^p\equiv a(\mathrm{mod}p)$

（ii）若$p$整除$a$，则显然有$p$整除$a^p$，即$a^p\equiv a\equiv 0(\mathrm{mod}p)$。

方法二

Template:Seealso 若$p$为质数，$n$为整数，且$p\ge n$。考慮二項式係數$(\genfrac{}{}{0ex}{}{p}{n})=\frac{p!}{n!(p-n)!}$，並限定$n$不為$p$或$0$，則由於分子有質數$p$，但分母不含$p$，故分子的$p$能保留，不被約分而除去，即$(\genfrac{}{}{0ex}{}{p}{n})$恆為$p$的倍數。

再考慮$(b+1{)}^p$的二項式展開，模$p$，則

$(b+1{)}^p\equiv (\genfrac{}{}{0ex}{}{p}{p})b^p+(\genfrac{}{}{0ex}{}{p}{p-1})b^{p-1}+(\genfrac{}{}{0ex}{}{p}{p-2})b^{p-2}+\dots +(\genfrac{}{}{0ex}{}{p}{2})b^2+(\genfrac{}{}{0ex}{}{p}{1})b^1+(\genfrac{}{}{0ex}{}{p}{0})b^0(\mathrm{mod}p)$

$\equiv (\genfrac{}{}{0ex}{}{p}{p})b^p+(\genfrac{}{}{0ex}{}{p}{0})b^0(\mathrm{mod}p)$

$\equiv b^p+1(\mathrm{mod}p)$

因此

$(b+1{)}^p\equiv b^p+1(\mathrm{mod}p)$

$\equiv (b-1{)}^p+1+1(\mathrm{mod}p)$

$\equiv (b-2{)}^p+1+1+1(\mathrm{mod}p)$

$\equiv (b-3{)}^p+1+1+1+1(\mathrm{mod}p)$

$\dots$

$\equiv \begin{array}{c}\underbrace{1+1+\dots +1+1}\\ b+1\end{array}(\mathrm{mod}p)$

$\equiv b+1(\mathrm{mod}p)$

令$a=b+1$，即得$a^p\equiv a(\mathrm{mod}p)$。

方法三

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

應用

• 計算$2^{100}$除以13的餘數

$2^{100}\equiv 2^{12\times 8+4}(\mathrm{mod}13)$

$\equiv (2^{12}{)}^8\cdot 2^4(\mathrm{mod}13)$

$\equiv 1^8\cdot 16(\mathrm{mod}13)$

$\equiv 16(\mathrm{mod}13)$

$\equiv 3(\mathrm{mod}13)$

故餘數為3。

• 證明對於任意整數a而言，$a^{13}-a$恆為2730的倍數。
  • 易由$a^{p-1}\equiv 1(\mathrm{mod}p)$推得$a^{n(p-1)+1}\equiv 1^n\cdot a\equiv a(\mathrm{mod}p)$，其中$n$為正整數。
  • 故對指數13操作如下：13減1為12，12的正因數有1, 2, 3, 4, 6, 12，分別加1，為2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13為質數，根據定理的延伸表達式，$a^{13}-a$為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數，即2*3*5*7*13=2730的倍數。

• 證明對於任意整數a而言，$a^{22}-a^2$恆為3300的倍數。

• $a^{22}-a^2$為132的倍數。
  1. 模仿前述操作，11減1為10，10的正因數有1, 2, 5, 10，分別加1，為2, 3, 6, 11，其中2, 3, 11為質數，因此$a^{11}-a$為2, 3, 11的最小公倍數的倍數，即66的倍數。
  2. 考慮$a^{11}+a$，因為奇數的11次方仍為奇數，且奇數與奇數之和為偶數，故當a為奇數時，$a^{11}+a$為偶數；同理可知當a為偶數時，$a^{11}+a$仍為偶數。因此當a為任意整數時，$a^{11}+a$為偶數。
  3. 因此$a^{22}-a^2=(a^{11}-a)(a^{11}+a)=66$的倍數$\times 2$的倍數$=132$的倍數。
• $a^{22}-a^2$為25的倍數。
  • 由後文的欧拉定理可知$a^{20}\equiv 1(\mathrm{mod}25)$（當a與25互質時），即$a^{21}\equiv a(\mathrm{mod}25)$（當a為任意整數時）。因此$a^{22}-a^2=a(a^{21}-a)$為25的倍數。
• 因此$a^{22}-a^2$為132與25的的最小公倍數的倍數，即3300的倍數。

推广

欧拉定理

费马小定理是欧拉定理的一个特殊情况：如果 $(a,n)=1$ ，那么

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

这里 $\phi (n)$ 是欧拉函数。欧拉函数的值是所有小于或等于 $n$ 的正整数中与 $n$ 互質的数的个数。假如 $n$ 是一个素数，则 $\phi (n)=n-1$ ，即费马小定理。

证明

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

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

卡邁克爾函數

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

$a^{\lambda (n)}\equiv 1(\mathrm{mod}n)$

多项式除法

因為$p|x^p-x\Rightarrow p^k|(x^p-x{)}^k$

所以由$x^N(\mathrm{mod}(x^p-x{)}^k)$的結果可以得出$x^N(\mathrm{mod}{p}^k)$的結果

用多項式除法可以得出$x^N$除以$(x^p-x{)}^k$的次數少於$p^k$的餘式

例如$3\mid x^3-x$，由多項式除法得到$x^5=(x^2+1)(x^3-x)+x$，則$x^5\equiv x(\mathrm{mod}3)$

這個餘式的一般結果是：

$x^{pk}\equiv \sum _{i=1}^k(-1{)}^{i-1}(\genfrac{}{}{0ex}{}{k}{i})x^{pk-(p-1)i}(\mathrm{mod}{p}^k)$（除式）

$x^{pk+(p-1)n}\equiv \sum _{i=1}^k(-1{)}^{i-1}(\genfrac{}{}{0ex}{}{n+i-1}{i-1})(\genfrac{}{}{0ex}{}{n+k}{k-i})x^{pk-(p-1)i}(\mathrm{mod}{p}^k)$

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

求$x^{1000}(\mathrm{mod}{5}^2)$

$x^{10+4n}\equiv (n+2)x^6-(n+1)x^2(\mathrm{mod}{5}^2)$

$x^{1000}\equiv 249x^8-248x^4\equiv 24x^8-23x^4(\mathrm{mod}{5}^2)$

参见

• 费马大定理
• 拉格朗日定理