費馬小定理

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

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

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

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

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

$$a^{p-1} \equiv 0 \pmod{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年以前已經得到幾乎是相同的證明。

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

### 卡邁克爾數

如前述，中國猜想是有反例的。符合中國猜想的條件但不是素數的數被稱為偽素數。

更極端的反例是卡邁克爾數：假設$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$，考慮$a, 2a, 3a,....(p-1)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,\ldots,(p-1) \}$的重新排列，即$1,2,3,\ldots,(p-1)$在餘數中各出現恰好一次；這是因為對於任兩個相異$ka$而言（$k=1,2,3,\ldots,(p-1)$），其差不是$p$的倍數（所以不會有相同餘數），且任一個$ka$亦不為$p$的倍數（所以餘數不為0）。因此

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

即

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

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

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

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

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

### 方法二

若$p$為質數，$n$為整數，且$1 \le n\le p-1$。考慮二項式係數$\tbinom{p}{n}=\tfrac{p!}{n!(p-n)!}$，因為$n$不為$p$或$0$，則由於分子有質數$p$，但分母不含$p$，故分子的$p$能保留，不被約分而除去，即$\tbinom{p}{n}$恆為$p$的倍數。

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

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

$$\equiv \dbinom{p}{p}a^p+ \dbinom{p}{0}a^0$$

$$\equiv a^p+1 \pmod{p}$$

因此

$$(a+1)^p \equiv a^p+1$$

$$\equiv (a-1)^p+1+1$$

$$\equiv (a-2)^p+1+1+1$$

$$\equiv (a-3)^p+1+1+1+1$$

$$\dots$$

$$\equiv \begin{matrix} \underbrace{1+1+\dots+1+1 } \\ a+1 \end{matrix}$$

$$\equiv a+1 \pmod{p}$$

因為$a^p+1 \equiv a+1 \pmod{p}$，兩邊同減1，即得$a^p \equiv a \pmod{p}$。

### 方法三

在抽象代數教科書中，費馬小定理常作為教授拉格朗日定理時的一個簡單例子。這裡只給出$a$不是$p$的倍數時 $a^{p-1} \equiv 1 \pmod{p}$的證明。

對於所有$p$的非倍數整數$b$，$\pmod{p}$的同餘集合對乘法構成一個群，記作：

$$\{\overline{1},\overline{2},\overline{3} , ... ,\overline{p-1}\}$$

$\overline{n}$ 為$\pmod{p}$餘數為$n$的所有整數集合（因為$b$不是$p$的倍數，所以不會出現$\overline{0}$）。這個群的階是 $p-1$，單位元為$\overline{1}$。根據群的基本原理可得:

$b^r \in \overline{1}$，（$r$為$b$的階），即$$b^r \equiv 1 \pmod{p}$$

根據拉格朗日定理（的推論），$r$ 必是群的階$p-1$的約數，可得$$b^{p-1} \equiv 1 \pmod{p}$$

$b$為所有$p$的非倍數整數，因此$$a^{p-1} \equiv 1 \pmod{p}$$

證畢。

## 應用

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

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

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

$$\equiv 1^8 \cdot 16$$

$$\equiv 16$$

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

故餘數為3。

- 證明對於任意整數a而言，$a^{13}-a$恆為2730的倍數。
- 易由$a^{p-1} \equiv 1 \pmod{p}$推得$a^{n(p-1)+1} \equiv 1^n \cdot a \equiv a \pmod{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的倍數。
- 模仿前述操作，11減1為10，10的正因數有1, 2, 5, 10，分別加1，為2, 3, 6, 11，其中2, 3, 11為質數，因此$a^{11}-a$為2, 3, 11的最小公倍數的倍數，即66的倍數。
- 考慮$a^{11}+a$，因為奇數的11次方仍為奇數，且奇數與奇數之和為偶數，故當a為奇數時，$a^{11}+a$為偶數；同理可知當a為偶數時，$a^{11}+a$仍為偶數。因此當a為任意整數時，$a^{11}+a$為偶數。
- 因此$a^{22}-a^2=(a^{11}-a)(a^{11}+a)=66$的倍數$\times 2$的倍數$=132$的倍數。
- $a^{22}-a^2$為25的倍數。
- 由後文的歐拉定理可知$a^{20} \equiv 1 \pmod {25}$（當a與25互質時），即$a^{21} \equiv a \pmod {25}$（當a為任意整數時）。因此$a^{22}-a^2=a(a^{21}-a)$為25的倍數。
- 因此$a^{22}-a^2$為132與25的的最小公倍數的倍數，即3300的倍數。

## 推廣

### 歐拉定理

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

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

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

證明

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

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

### 卡邁克爾函數

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

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

### 多項式除法

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

所以由$x^N\pmod{(x^p-x)^k}$的結果可以得出$x^N\pmod{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\pmod{3}$

這個餘式的一般結果是：

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

$$\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時為除式，用數學歸納法證明餘式。

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

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

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