关于费马小定理的证明
wusixuan
·
·
算法·理论
费马小定理：设 p 为素数，a 是任意整数且 a \not\equiv 0 (\bmod p)。
我们可以考虑证明特殊数字的情况，再从特殊数推到一般性证明。
考虑证明 3^6 \equiv 1(\bmod 7)，为证明它，我们由数 1,2,3,4,5,6 分别乘以 3 然后对 7 取模的结果列入下表：
| x(\bmod 7) |
1 |
2 |
3 |
4 |
5 |
6 |
| 3x(\bmod 7) |
3 |
6 |
2 |
5 |
1 |
4 |
注意每个数 1,2,3,4,5,6 在第二行和第二行都恰好出现了一次。所以，如果将第二行和第一行中数字乘起来，一定是相同的结果。因此：
(3\times 1)(3\times2)(3\times3)(3\times4)(3\times5)(3\times6)\equiv1\times2\times3\times4\times5\times6(\bmod7)
整理可得：
3^6\times6!\equiv6!(\bmod 7)
---
接下来准备证明一般性的费马小定理。我们可以推出 $3^6 \equiv (\bmod 7)$ 关键是 $1$ 到 $6$ 的所有数，乘以 $3$ 后重新排列。所以我们先验证下述命题：
**命题**：设 $p$ 为素数，$a$ 是任意整数且 $a \not\equiv 0 (\bmod p)$，则数
$$
a,2a,3a,···,(p-1)a
$$
对 $p$ 取模与数
$$
1,2,3,···,p-1
$$
相同，允许次序不同。
**证明**：假设从数列 $a,2a,3a,···,(p-1)a$ 里面选择两个不同的数 $xa$ 和 $ya$，并且假设它们同余，即 $xa \equiv ya(\bmod p)$。数列中显然没有一个数被 $p$ 整除，所以 $xa,ya$ 为正整数。
可得出 $p | (x-y)a$，因为 $p$ 不整除 $a$，所以 $p | (x-y)$。由于 $1 \le x,y \le p-1$，所以 $|x-y| < p-1$，显然只有 $0 < p-1$ 且被 $p$ 整除，但是 $x\not=y$，也就是不可能选择一个 $xa$ 和一个 $ya$。
这表明 $a,2a,3a,···,(p-1)a$ 中，任意两个元素之间对 $p$ 取模都是不同的，由于取模后的取值范围是 $1$ 到 $p-1$，而 $1$ 到 $p-1$ 又有 $p-1$ 个数，因此刚好为 $a,2a,3a,···,(p-1)a$ 对 $p$ 取模的结果，所以命题是成立的。
---
得到命题就可以容易的得到费马小定理证明：
由于命题成立，所以
$$
a\times(2a)\times(3a)\times···\times ((p-1)a)\equiv1\times2\times3\times···\times(p-1)(\bmod p)
$$
整理得
$$
a^{p-1}\times (p-1)!\equiv(p-1)!(\bmod p)
$$
由于 $(p-1)!$ 与 $p$ 互素，约掉 $(p-1)!
a^{p-1} \equiv 1(\bmod p)
正好为费马小定理，证毕。