フェルマーの小定理

写像 $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$ を得る。