费马小定理

费马小定理（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$，不是质数。满足费马小定理的合数被称为费马伪素数。

## 历史

<image>

皮埃尔·德·费马于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}$$