第 213 页 / 10.4 环与域

定理 10.15 (费马小定理) 如果 p 为素数, 则对所有 n≠0 (mod p) 有 n^{p-1}≡1 (mod p).
证明 对于费马小定理有一个简单的组合证明. 考虑用 n 种颜色对具有 p 颗珠子的手镯进行着色. 这些珠子标记为 1, 2, …, p, 等距离地顺序排列在圆环上, 图 10.4 给出了 5 个珠子的一个实例. 令 θ=2π/p, 当手镯旋转的角度分别等于 θ, 2θ, …, pθ. 由于 p 是素数, 除了 pθ=2π 对应于恒等置换之外, 其他 p-1 个置换都由一个 p 阶轮换构成[a]. 根据 Polya 定理, 不同的着色方案数是

M = \frac{1}{p} [n^p + (p-1)n^1] = \frac{1}{p}(n^p-n) +n

因为 M 和 n 是正整数, 因此 n^p-n = n(n^{p-1}-1) 能被 p 整除[b], 即

n^{p-1} ≡ 1 (mod p)
这个证明方法外文称为 proof by counting necklaces.[1] 中文网络上很难找到这个证法的说明, 因为都是从欧拉定理出发来证明费马小定理(FlT)的.
这个证明过程确实推导出  n^{p-1} ≡ 1 (mod p) 这个最终结论, 却没有清楚说明 为什么可以利用这个恒等式判定 p 是或者不是素数.
因为费马小定理存在伪素数的情况, 这个证明过程没有在开头显式声明 "假设 p 是素数"(但是后面又有 "因为 p 是素数" 这样的字眼), 这个证明实质上是对必要性的证明, 于是看起来比较晦涩难懂.
[a] 处, 只有当 p 是素数时其置换群具有 1×p+(p-1)×1 的形式. 随便拎一个反例, 比如 p=4, 其置换群为 {(1), (1,2,3,4), (1,3)(2,4), (4,3,2,1)}, 其 Polya 式为 M=(1/4)*[n^4+n^2+2n], 不能再向下推导.
更一般地, 对于 p 不是素数的情况, 有 M=(1/p)[n^p + P_{p-1}(n)], P是多项式. 比较系数可知, 假如恰有 P=(p-1)n, 则符合 p 是素数的情形. 这是伪素数的来源之一.(我的猜想, 没有动手证明)
[b] 处, 有:
     M = \frac{1}{p} [n^p + (p-1)n^1] = \frac{1}{p}(n^p-n) +n 
⇔ (M-n)*p = n * (n^{p-1}-1)
引文已经说明 M-n, p 都为整数, 所以有 
n * (n^{p-1}-1) ≡ 0 (mod p)
根据同余定理(在本书19.1节以及性质19.7, 在[Ke14]则排在比较靠前的第三章)有三种情况:
    1. n ≡ 0 (mod p)
    与题设 n, p 互素矛盾, 排除.
    2. n^{p-1}-1 ≡ 0 (mod p)
    即费马小定理的最终结论.
    3. 以上两者都不能整除 p, 但两者至少其一是 (mod p) 的零因子. (按上述性质)此时 p 是合数. 这是伪素数的第二个来源(也没有证明).
=======
参考文献
[1] Brent, Fermat's Little Theorem: proof by necklaces, 2017. https://mathlesstraveled.com/2017/12/12/fermats-little-theorem-proof-by-necklaces/
[Ke14] Kenneth H. Rosen, 离散数学及其应用, 机械工业出版社, 2014.