费马小定理

费马小定理说：若 $p$ 是素数、整数 $a$ 不被 $p$ 整除，则 $a^{p - 1} \equiv 1 (\mod p) .$ 另一种等价写法是对任意整数 $a$ 有 $a^{p} \equiv a (\mod p)$ ；当 $p ∣ a$ 时后一式两边都余 0，前一式则不能使用。

将非零余数重新排列

模 $p$ 的非零剩余类为 $1, 2, \dots, p - 1$ 。乘以 $a$ 后得到 $a, 2 a, \dots, (p - 1) a$ ；这些余数互不相同，因为若 $a i \equiv a j$ ， $a$ 与 $p$ 互素，便可约去 $a$ 得 $i \equiv j$ 。于是新名单恰是旧名单的排列，两个名单乘积相等： $a^{p - 1} (p - 1)! \equiv (p - 1)! (\mod p) .$ 阶乘中的每个因子都与 $p$ 互素，故可约去，得到定理。

取 $p = 11, a = 2$ ，有 $2^{10} = 1024 = 11 \cdot 93 + 1$ 。这个算例核对了结果，却不能替代对任意素数的排列证明。不能把“ $a^{n - 1} \equiv 1 (\mod n)$ ”倒过来作为素数判据：合数 $341 = 11 \cdot 31$ 也满足 $2^{340} \equiv 1 (\mod 341)$ ，因为 $2^{10} = 1024 \equiv 1 (\mod 341)$ ，再取 34 次方即可。

参考资料

MIT，Mathematics for Computer Science，Number Theory 章节。
MIT 18.781，初等数论讲义。
继续阅读：素数、模逆元、欧拉定理。