费马小定理

1. 定义

假如 ${\displaystyle a}$ 是一个整数，${\displaystyle p}$是一个质数，那么 ${\displaystyle a^{p}-a}$ 是 $p$ 的倍数，可以表示为

$$\begin{array}{c} a^p \equiv a \,\, (mod \,\, p) \end{array}$$

如果 $a$ 不是 $p$ 的倍数，这个定理也可以写成

$$\begin{array}{c} a^{p-1} \equiv 1 \,\, (mod \,\, p) \end{array}$$

2. 证明

• 对于 $a = 0$ 的情况，定义中的第一个等式显然成立。
• 对于 $a \ne 0$ 的情况，则 $(a,p) = 1$。此时模 $p$ 的所有非零的余数，在同于意义下对乘法构成一个群，此群的阶是 $p-1$。根据群论中的拉格朗日定理，对于该群中的 $\forall x$，都有 $x$ 的阶必整除群的阶，故命题得证。

3. 推广

• 费马小定理是欧拉定理的一个特殊情况。
• 卡迈克尔函数比欧拉函数更小，费马小定理也是它的特殊情况。它的特殊情况。