费马小定理

**費馬小定理**（英語：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$ 的倍數， $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×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$ ，考慮 $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,\ldots ,(p-1)\}$ 的重新排列，即 $1,2,3,\ldots ,(p-1)$ 在餘數中恰好各出現一次；這是因為對於任兩個相異 $k*a$ 而言（ $k=1,2,3,\ldots ,(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){\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$ 為整數，且 $p\geq n$ 。考慮二項式係數 ${\tbinom {p}{n}}={\tfrac {p!}{n!(p-n)!}}$ ，並限定 $n$ 不為 $p$ 或 $0$ ，則由於分子有質數 $p$ ，但分母不含 $p$ ，故分子的 $p$ 能保留，不被約分而除去，即 ${\tbinom {p}{n}}$ 恆為 $p$ 的倍數。

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

　
: $(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}}$

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

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

因此

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

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

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

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

　
: $\dots $

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

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

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

### 方法三

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

## 應用

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

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

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

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

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

　
: $\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,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}}}
$$

## 注釋

## 參見

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

## 參考