费马小定理

映射 $k\mapsto ak\bmod p$ 是 $\{1,\dots,p-1\}$ 上的一个置换,因为 $a$ 模 $p$ 可逆(由 $p\nmid a$)。把所有剩余相乘得 $\prod_{k=1}^{p-1}(ak) \equiv \prod_{k=1}^{p-1} k \pmod p$,即 $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$。由于 $\gcd((p-1)!,p)=1$,消去后得 $a^{p-1}\equiv 1\pmod p$。