フェルマーの小定理

法$p$に関する非零の剰余の集合$S=\{1,2,\dots,p-1\}$と、$S$の各元を剰余へ送る写像$x \mapsto ax \bmod p$を考える。

この写像は$S$上で単射である:$x,y\in S$について$ax\equiv ay\pmod p$ならば、$\gcd(a,p)=1$なので、簡約法則(前のトピックで証明済み)により$x\equiv y\pmod p$、したがって両者とも$\{1,\dots,p-1\}$に属するので$x=y$である。また$x\in S$に対して$ax$ が $\equiv 0\pmod p$ となることもない。なぜなら$p$は素数であり$a$も$x$も割り切らないからである。よってこの写像は実際に$S$の中に収まる。

有限集合$S$からそれ自身への単射写像は自動的に全単射である。したがって$\{a\cdot1,a\cdot2,\dots,a\cdot(p-1)\} \pmod p$は、単に$\{1,2,\dots,p-1\}$を別の順序で並べたものにすぎない。

両方の集合の$p-1$個すべての元を掛け合わせる。一方では$(a\cdot1)(a\cdot2)\cdots(a\cdot(p-1)) = a^{p-1}\,(p-1)!$が得られ、もう一方では同じ数を並び替えただけなのでちょうど$(p-1)!$が得られる。よって$a^{p-1}(p-1)! \equiv (p-1)! \pmod p$。

$p$は素数なので、$1,2,\dots,p-1$のどれも$p$で割り切れず、$\gcd((p-1)!,p)=1$である。両辺から共通因子$(p-1)!$を取り除くためにもう一度簡約法則を適用すると$a^{p-1}\equiv1\pmod p$が得られる。$\blacksquare$

(群論的な言い換え:$p$が素数なので非零の剰余は乗法の下で位数$p-1$の群をなし、ラグランジュの定理により任意の元の位数——ここでは$a^k\equiv1$となる最小の$k$——は群の位数$p-1$を割り切らなければならない;したがって$a^{p-1}\equiv1\pmod p$が自動的に成り立つ。)