費馬小定理

費馬小定理（英語：Fermat's little theorem）是數論中的一個定理。假如${\displaystyle a}$是一個整數，${\displaystyle p}$是一個質數，那麼${\displaystyle a^{p}-a}$是${\displaystyle p}$的倍數，可以表示為

${\displaystyle a^{p}\equiv a{\pmod {p}}}$

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

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$^{[1][註 1]}

註：如果${\displaystyle a}$是${\displaystyle p}$的倍數，則

${\displaystyle a^{p-1}\equiv 0{\pmod {p}}}$

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

歷史

皮埃爾·德·費馬

皮埃爾·德·費馬於1636年發現了這個定理。在一封1640年10月18日的信中他第一次使用了上面的書寫方式。在他的信中費馬還提出a是一個質數的要求。

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

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

卡邁克爾數

主條目：卡邁克爾數

如上所述，中國猜想僅有一半是正確的。符合中國猜想但不是質數的數被稱為偽質數。

更極端的反例是卡米高數： 假設${\displaystyle a}$與561互質，則${\displaystyle a^{560}}$被561除都餘1。這樣的數被稱為卡邁克爾數，561是最小的卡邁克爾數。Korselt在1899年就給出了卡邁克爾數的等價定義，但直到1910年才由卡邁克爾（Robert Daniel Carmichael）發現第一個卡邁克爾數：561。1994年William Alford、Andrew Granville及Carl Pomerance證明了卡邁克爾數有無窮多個。

證明

方法一

（i）若${\displaystyle a}$是整數，${\displaystyle p}$是質數，且${\displaystyle \gcd(a,p)=1}$。若${\displaystyle p}$不能整除${\displaystyle x-y}$，則${\displaystyle p}$不能整除${\displaystyle a(x-y)}$。取整數集${\displaystyle A}$為所有小於${\displaystyle p}$的正整數集合（${\displaystyle A}$構成${\displaystyle p}$的完全剩餘系，即${\displaystyle A}$中不存在兩個數同餘${\displaystyle p}$），${\displaystyle B}$是${\displaystyle A}$中所有的元素乘以${\displaystyle a}$組成的集合。因為${\displaystyle A}$中的任何兩個元素之差都不能被${\displaystyle p}$整除，所以${\displaystyle B}$中的任何兩個元素之差也不能被${\displaystyle p}$整除。

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

${\displaystyle 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){\pmod {p}},}$

即

${\displaystyle W\equiv W\cdot a^{p-1}{\pmod {p}},}$

在這裏${\displaystyle W=1\cdot 2\cdot 3\cdot \ldots \cdot (p-1)}$，且${\displaystyle (W,p)=1}$，因此將整個公式除以${\displaystyle W}$即得到：

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$^[3]

也即 ${\displaystyle a^{p}\equiv a{\pmod {p}}}$

（ii）若${\displaystyle p}$整除${\displaystyle a}$，則顯然有${\displaystyle p}$整除${\displaystyle a^{p}}$，即${\displaystyle a^{p}\equiv a\equiv 0{\pmod {p}}}$。

方法二

參見：中一新生之夢

若${\displaystyle p}$為質數，${\displaystyle n}$為整數，且${\displaystyle p\geq n}$。考慮二項式系數${\displaystyle {\tbinom {p}{n}}={\tfrac {p!}{n!(p-n)!}}}$，並限定${\displaystyle n}$不為${\displaystyle p}$或${\displaystyle 0}$，則由於分子有質數${\displaystyle p}$，但分母不含${\displaystyle p}$，故分子的${\displaystyle p}$能保留，不被約分而除去，即${\displaystyle {\tbinom {p}{n}}}$恆為${\displaystyle p}$的倍數^[4]。

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

${\displaystyle (b+1)^{p}\equiv {\dbinom {p}{p}}b^{p}+{\dbinom {p}{p-1}}b^{p-1}+{\dbinom {p}{p-2}}b^{p-2}+\dots +{\dbinom {p}{2}}b^{2}+{\dbinom {p}{1}}b^{1}+{\dbinom {p}{0}}b^{0}{\pmod {p}}}$

${\displaystyle \equiv {\dbinom {p}{p}}b^{p}+{\dbinom {p}{0}}b^{0}{\pmod {p}}}$

${\displaystyle \equiv b^{p}+1{\pmod {p}}}$

因此

${\displaystyle (b+1)^{p}\equiv b^{p}+1{\pmod {p}}}$

${\displaystyle \equiv (b-1)^{p}+1+1{\pmod {p}}}$

${\displaystyle \equiv (b-2)^{p}+1+1+1{\pmod {p}}}$

${\displaystyle \equiv (b-3)^{p}+1+1+1+1{\pmod {p}}}$

${\displaystyle \dots }$

${\displaystyle \equiv {\begin{matrix}\underbrace {1+1+\dots +1+1} \\b+1\end{matrix}}{\pmod {p}}}$

${\displaystyle \equiv b+1{\pmod {p}}}$

令${\displaystyle a=b+1}$，即得${\displaystyle a^{p}\equiv a{\pmod {p}}}$。^[3]

方法三

在抽象代數教科書中，費馬小定理常作為教授拉格朗日定理時的一個簡單例子^[5]。顯然只需考慮 ${\displaystyle (a,p)=1}$ 情形。此時模 ${\displaystyle p}$ 所有非零的餘數，在同餘意義下對乘法構成一個群，這個群的階是 ${\displaystyle p-1}$。考慮群中的任何一個元素 ${\displaystyle b}$，根據拉格朗日定理，${\displaystyle b}$ 的階必整除群的階。證畢。

應用

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

${\displaystyle 2^{100}\equiv 2^{12\times 8+4}{\pmod {13}}}$

${\displaystyle \equiv (2^{12})^{8}\cdot 2^{4}{\pmod {13}}}$

${\displaystyle \equiv 1^{8}\cdot 16{\pmod {13}}}$

${\displaystyle \equiv 16{\pmod {13}}}$

${\displaystyle \equiv 3{\pmod {13}}}$

故餘數為3。

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

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

證明

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

推廣

歐拉定理

費馬小定理是歐拉定理的一個特殊情況：如果 ${\displaystyle (a,n)=1}$ ，那麼

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

這裏 ${\displaystyle \varphi (n)}$ 是歐拉函數。歐拉函數的值是所有小於或等於 ${\displaystyle n}$ 的正整數中與 ${\displaystyle n}$ 互質的數的個數。假如 ${\displaystyle n}$ 是一個質數，則 ${\displaystyle \varphi (n)=n-1}$ ，即費馬小定理。

證明

上面證明費馬小定理的群論方法，可以同理地證明歐拉定理。

考慮所有與 ${\displaystyle n}$ 互質的數，這些數模 ${\displaystyle n}$ 的餘數所構成的集合，記為 ${\displaystyle {\cal {S}}}$，並將群乘法定義為相乘後模 ${\displaystyle n}$ 的同餘。顯然 ${\displaystyle {\cal {S}}}$ 是一個群，因為它對群乘法封閉（若 ${\displaystyle (a,n)=1}$ 和 ${\displaystyle (b,n)=1}$ 則 ${\displaystyle (ab,n)=1}$），含單位元素（即「1」），且任何一個元素 ${\displaystyle a}$ 的反元素也在集合中（因為若 ${\displaystyle a\in {\cal {S}}}$ 則由群乘法封閉性任何${\displaystyle a}$ 的冪次都在 ${\displaystyle {\cal {S}}}$ 中，所以 ${\displaystyle \langle a\rangle }$ 是 ${\displaystyle {\cal {S}}}$ 這個有限集的子集）。根據定義， ${\displaystyle {\cal {S}}}$ 的階是 ${\displaystyle \varphi (n)}$，於是根據拉格朗日定理， ${\displaystyle {\cal {S}}}$ 中任何一個元素的階必整除 ${\displaystyle \varphi (n)}$。證畢。

卡邁克爾函數

主條目：卡邁克爾函數

卡邁克爾函數比歐拉函數更小。費馬小定理也是它的特殊情況。

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

多項式除法

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

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

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

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

這個餘式的一般結果是：

${\displaystyle \displaystyle x^{pk}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}x^{pk-(p-1)i}{\pmod {p^{k}}}}$（除式）

${\displaystyle \displaystyle x^{pk+(p-1)n}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {n+i-1}{i-1}}{\binom {n+k}{k-i}}x^{pk-(p-1)i}{\pmod {p^{k}}}}$

n=0時為除式，用數學歸納法證明餘式。^[6]

求${\displaystyle x^{1000}{\pmod {5^{2}}}}$

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

${\displaystyle x^{1000}\equiv 249x^{8}-248x^{4}\equiv 24x^{8}-23x^{4}{\pmod {5^{2}}}}$

註釋

1. 符號的應用請參見同餘和模算數。

參見

• 費馬大定理
• 拉格朗日定理

參考

1. Fermat's Little Theorem （頁面存檔備份，存於互聯網檔案館）.WolframMathWorld.（英文）
2. A proof of certain theorems regarding prime numbers. [2012-12-11]. （原始內容存檔於2015-06-16）.
3. 許介彥. 費馬小定理 (PDF). 科學教育月刊 (私立大葉大學電機工程學系). 2006年10月, (第293期): 37–44 [2015-04-18]. （原始內容 (PDF)存檔於2015-04-18）.
4. How is (x+y)^p≡x^p+y^p mod p for any prime number p. Mathematics Stack Exchange. 2018-09-27 [2021-04-26]. （原始內容存檔於2022-03-25） （英語）.
5. 聶靈沼; 丁石孫. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33頁. ISBN 7-04-008893-2. 使用|accessdate=需要含有|url= (幫助)
6. 黃嘉威. 多项式除法解高次同余. 數學學習與研究. 2015, (9): 第104頁 [2015-07-19]. （原始內容存檔於2020-10-20）.