同余运算和费马小定理的证明

SICP 一书 1.2.6 小节提到费马检查和费马小定理，但没有小定理的证明。此文补充这个证明。

同余运算

以数学符号来描述，假如 $a\bmod n == b\bmod n$ ，两者同余，记为

$a \equiv b\pmod n$

同余等价符号是三个横线的等号。另外数学符号 a mod n 是一个整体，表示 a 对 n 求模（取余数），没有像函数调用那样记成 mod(a, n)。

同余有些很好的性质。有加法原理和乘法原理。

$(a+b)\bmod n = [(a\bmod n)+(b\bmod n)]\bmod n$

$ab\bmod n = [(a\bmod n)(b\bmod n)]\bmod n$

mod 运算，可看成是时钟转圈，超出一圈又会绕到原来的地方。

在同余的公式中，经常会出现 mod 运算，似乎很复杂。但只要将 a 看成是跟 $a\bmod n$ 等价，公式就会很自然了。

出现 mod 都是为了让 a 转几圈之后，重新落入到 [0, n) 的区间之下。这样参与运算的数字会在 [0, n) 中，结果也会封闭在 [0, n) 中，永远不会超出这个范围。

比如乘法性质，先将 a 看成等价的 $a\bmod n$ , b 看成等价的 $b\bmod n$ ，之后再相乘，乘出来的结果再算 mod, 重新落入 [0, n) 区间中。

只要将 a 看成是跟 $a\bmod n$ 等价，同余的很多运算性质几乎就跟普通整数运算一样。

代码 expmod 计算幂取模运算，其实应用了同余的乘法原理。

当 b 为奇数时

$a^b\bmod n = aa^{b-1}\bmod n= [(a\bmod n)(a^{b-1}\bmod n)]\bmod n$

当 b 为偶数时

$a^b\bmod n = a^{b/2}a^{b/2}\bmod n= (a^{b/2}\bmod n)^{2}\bmod n$

费马小定理说，当 n 为素数，a < n （或者 a, n 两者互质）时，有

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

我们通常会变换一下公式，两边除以 a，等价于

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

--------------------

要证明费马小定理，先要证明一个结论。假如 n 是一个素数，a < n, 这样排列 1、2、3、4、5 .. n - 1, 乘以 a, 再取 n 的余数，结果也是 1 到 n - 1 的排列，但是顺序会打乱。

举个例子 n = 5, a = 3。

可以看到，余数仍然是 1 到 4 之间，没有重复，只是顺序打乱了。

反证法。假如结论不成立的话，就会有 i, j 两个数字，使得

$i * a \equiv j * a\pmod n$

不妨假设 i > j，将上式移动一下位置，就会有

$(i - j) * a \equiv 0\pmod n$

换句话说，就是 (i - j) * a 可以被 n 整除。而 n 是素数，那么 (i - j) 或者 a 其中之一就必须包含因子 n。但 (i - j) 和 a 都比 n 要小，显然不可能包含因子 n。于是结论得证。

上面的证明中，不一定需要 a < n。只要 n 为素数，而 a, n 两者互质，证明也可成立，费马小定理也可成立。

--------------------

因为乘以 a 再 mod n，只是 1 到 n - 1 的重新排列，数字并不会重复。于是我们就可以知道

$(1 * 2 * 3 .... n - 1) = (a\bmod n)(2a\bmod n)(3a\bmod n) ... ((n-1)a\bmod n)$

应用同余的乘法原理，使用同余的记号，可以将上式记为

$(1 * 2 * 3 .... n - 1) \equiv a * 2a * 3a * ... (n-1)a\pmod n$

将上式同时除以 $(1 * 2 * 3 .... n - 1)$ ，费马小定理得证

$a^{n-1}\equiv 1\mod n$