フェルマーの小定理とオイラーの定理

素数$p$を法とする非零の剰余は乗法の下で閉じた系をなす:固定した$a$をそのすべてに掛けることは、それらを互いにシャッフルするだけである。このシャッフルを$p-1$回繰り返すと、すべての要素が自身の位置に戻らなければならず、それがまさに$a^{p-1}\equiv1\pmod p$という主張である。

法$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$が自動的に成り立つ。)

これはまさにフェルマーの議論を一般の法$n$に適用したものである:($n$が素数のときのみ乗法的に閉じた系をなす)すべての非零剰余の代わりに、実際に$n$と互いに素な剰余——逆元を持つもの——に限定し、同じシャッフルの議論をサイズ$\varphi(n)$のこのより小さな閉じた集合に適用する。

法$n$に関する被約剰余系$R=\{r_1,\dots,r_{\varphi(n)}\}$を取る:$n$と互いに素なすべての剰余類の代表元である。

$a$による乗法は$R$を置換する:各$r_i$について、$\gcd(a,n)=1$かつ$\gcd(r_i,n)=1$なので$\gcd(ar_i,n)=1$である(積が$n$と互いに素であるのは両方の因数がそうであるとき、かつそのときに限る)。したがって$ar_i \bmod n$も互いに素な剰余類の一員である。また写像$r_i\mapsto ar_i \bmod n$は、$\gcd(a,n)=1$なので簡約法則により単射である。

有限集合$R$からそれ自身への(剰余の意味での)単射写像は全単射であるから、$\{ar_1,\dots,ar_{\varphi(n)}\} \pmod n$は単に$\{r_1,\dots,r_{\varphi(n)}\}$を並べ替えたものである。

各集合の$\varphi(n)$個すべての元を掛け合わせると:$a^{\varphi(n)}\, (r_1 r_2\cdots r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$。各$r_i$は$n$と互いに素なので、その積$R=\prod r_i$も互いに素、すなわち$\gcd(R,n)=1$である。

両辺から$R$を約分すると($\gcd(R,n)=1$なので有効)$a^{\varphi(n)}\equiv1\pmod n$が得られる。$\blacksquare$

これも姿を変えたラグランジュの定理である:$n$と互いに素な剰余は乗法の下で位数$\varphi(n)$の群(単数群$(\mathbb{Z}/n\mathbb{Z})^{*}$)をなし、任意の元の位数は$\varphi(n)$を割り切る。