§A4.7フェルマーの小定理とオイラーの定理

証明.$1\le i,j\le p-1$を満たす整数$i,j$を取る。$p\nmid i$かつ$p\nmid a$なので、§A4.2 補題 2.1により$p\nmid ia$である。したがって$ia$の法$p$における余りは$1,2,\ldots,p-1$のいずれかである。$ia\equiv ja\pmod p$ならば$p\mid(i-j)a$であり、同じ補題と$p\nmid a$から$p\mid i-j$を得る。$1\le i,j\le p-1$なので$|i-j|<p$であり、$i=j$となる。よって$a,2a,\ldots,(p-1)a$の余りは互いに異なり、$1,2,\ldots,p-1$の並べ替えになる。

両方の積を取ると

を得る。§A4.2 補題 2.1を繰り返し用いると、$p$は$(p-1)!$を割り切らないので、$\gcd((p-1)!,p)=1$である。したがって§A4.5 命題 3.2により$(p-1)!$を消去して、$a^{p-1}\equiv1\pmod p$を得る。▨

証明.$1$以上$n$以下で$n$と互いに素な整数を$r_1,\ldots,r_{\varphi(n)}$とする。各$ar_i$は$n$と互いに素である。実際、$n$と$ar_i$に共通する素因数があれば、§A4.2 補題 2.1により、その素数は$a,r_i$のどちらかを割り切り、$\gcd(a,n)=\gcd(r_i,n)=1$に反する。$ar_i$の法$n$における余りも$n$と互いに素であるので、その余りは$r_1,\ldots,r_{\varphi(n)}$のいずれかに等しい。$ar_i\equiv ar_j\pmod n$ならば、$\gcd(a,n)=1$と§A4.5 命題 3.2によって$a$を消去して$r_i\equiv r_j\pmod n$を得る。$r_i,r_j$は$1$以上$n$以下なので$|r_i-r_j|<n$であり、$r_i=r_j$となる。したがって、$ar_1,\ldots,ar_{\varphi(n)}$の余りは$r_1,\ldots,r_{\varphi(n)}$の並べ替えになる。

$R=r_1\cdots r_{\varphi(n)}$とおく。両方の積を取ると

を得る。各$r_i$は$n$と互いに素なので、§A4.2 補題 2.1を繰り返し用いると、$n$のどの素因数も$R$を割り切らない。よって$\gcd(R,n)=1$であり、§A4.5 命題 3.2により$R$を消去して$a^{\varphi(n)}\equiv1\pmod n$を得る。▨

証明.定理 2.2により$a^{\varphi(n)}\equiv1\pmod n$である。両辺に$a^k$を掛けると、最初の合同式を得る。$m=q\varphi(n)+r$、$q\ge0$、$0\le r<\varphi(n)$と書くと、

である。▨

証明.$n$が素数であれば、$\gcd(a,n)=1$から$n\nmid a$となり、定理 1.1により$a^{n-1}\equiv1\pmod n$となる。したがって、仮定を満たす$a$が存在するとき、$n$は素数ではない。$n\ge2$なので、$n$は合成数である。▨