Eulerの定理(整数論)

各 $ar_i$ は $n$ と互いに素である。$a$ も $r_i$ も $n$ と互いに素なので、互いに素 の記事の命題「互いに素な因子の消去」の 2 により $\gcd(ar_i,n)=1$ である。
次に $ar_i\equiv ar_j\pmod n$ とすると $n\mid a(r_i-r_j)$ であり、$\gcd(a,n)=1$ なので同じ命題の 1 により $n\mid r_i-r_j$、すなわち $r_i\equiv r_j\pmod n$ である。既約剰余系の定義から $i=j$ である。よって $ar_1,\dots,ar_{\varphi(n)}$ は $n$ と互いに素な $\varphi(n)$ 個の整数で、どの 2 つも合同でなく、既約剰余系である。$\square$

$b=1+p^et$（$t\in\mathbb{Z}$）と書く。二項定理により
$$ b^p=1+\binom p1p^et+\sum_{k=2}^{p}\binom pk p^{ek}t^k=1+p^{e+1}t+\sum_{k=2}^{p}\binom pk p^{ek}t^k $$
である。$k\ge2$ なら $ek\ge2e\ge e+1$ なので、和の各項は $p^{e+1}$ で割り切れる。よって $b^p\equiv1\pmod{p^{e+1}}$ である。$\square$

$r_1,\dots,r_{\varphi(n)}$ を法 $n$ の既約剰余系とする。$n$ と互いに素な整数はどれも、$r_1,\dots,r_{\varphi(n)}$ のちょうど 1 つと合同である（互いに素かどうかは法 $n$ の剰余類だけで決まり、$n$ と互いに素な剰余類は $\varphi(n)$ 個しかないので、合同でない $\varphi(n)$ 個の代表はそれらを 1 つずつ代表する）。lem-euler-theorem-permutation により、$ar_1,\dots,ar_{\varphi(n)}$ も既約剰余系なので、各 $ar_i$ はちょうど 1 つの $r_j$ と合同であり、$i\mapsto j$ は $\{1,\dots,\varphi(n)\}$ の並べ替えである。合同式は積と両立する（合同式 の記事の命題「合同式の和・差・積・冪」）ので、積をとって
$$ a^{\varphi(n)}\,r_1r_2\cdots r_{\varphi(n)}=(ar_1)(ar_2)\cdots(ar_{\varphi(n)})\equiv r_1r_2\cdots r_{\varphi(n)}\pmod n $$
である。$P:=r_1\cdots r_{\varphi(n)}$ は $n$ と互いに素な数の積なので $n$ と互いに素である（「互いに素な因子の消去」の 2 を繰り返す）。$n\mid(a^{\varphi(n)}-1)P$ と $\gcd(P,n)=1$ から、同じ命題の 1 により $n\mid a^{\varphi(n)}-1$ である。$\square$

$n=1$ は自明なので $n\ge2$ とし、$n=p_1^{e_1}\cdots p_r^{e_r}$ を素因数分解とする（$p_i$ は相異なる素数、$e_i\ge1$）。$\gcd(a,n)=1$ なので、どの $p_i$ も $a$ を割り切らない。
まず素数 $p\nmid a$ と $e\ge1$ について $a^{\varphi(p^e)}\equiv1\pmod{p^e}$ を、$e$ に関する帰納法で示す。Eulerのφ関数 の記事の例「素数と素数冪」により $\varphi(p^e)=p^{e-1}(p-1)$ である。$e=1$ では $\varphi(p)=p-1$ で、Fermatの小定理 そのものである。$a^{p^{e-1}(p-1)}\equiv1\pmod{p^e}$ と仮定すると、lem-euler-theorem-prime-power を $b=a^{p^{e-1}(p-1)}$ に使って $a^{p^e(p-1)}=b^p\equiv1\pmod{p^{e+1}}$ となる。
次に、Eulerのφ関数 の記事の定理「Eulerのφ関数の乗法性」により $\varphi(n)=\varphi(p_1^{e_1})\cdots\varphi(p_r^{e_r})$ なので、各 $i$ について $\varphi(n)$ は $\varphi(p_i^{e_i})$ の倍数である。$\varphi(n)=\varphi(p_i^{e_i})c_i$ と書けば
$$ a^{\varphi(n)}=\bigl(a^{\varphi(p_i^{e_i})}\bigr)^{c_i}\equiv1\pmod{p_i^{e_i}} $$
である。$p_1^{e_1},\dots,p_r^{e_r}$ はどの 2 つも互いに素で、$a^{\varphi(n)}-1$ はそのすべてで割り切れるので、その積 $n$ で割り切れる（合同式 の記事の命題「法を変える」の 2 を $r-1$ 回使う）。$\square$

$p$ は素数なので、$p$ の約数は $\pm1,\pm p$ だけであり、$p\nmid a$ から $\gcd(a,p)=1$ である。また $1,\dots,p-1$ はすべて $p$ と互いに素で $p$ は互いに素でないので $\varphi(p)=p-1$ である。thm-euler-theorem を $n=p$ に使えばよい。$\square$

$d\mid m$ なら $m=dk$ で、$a^m=(a^d)^k\equiv1^k=1$ である。逆に $a^m\equiv1$ とし、除法の原理で $m=dk+s$（$0\le s< d$）と書くと
$$ 1\equiv a^m=(a^d)^k\,a^s\equiv a^s\pmod n $$
である。$0< s< d$ なら $d$ の最小性に反するので $s=0$、すなわち $d\mid m$ である。thm-euler-theorem により $a^{\varphi(n)}\equiv1$ なので $d\mid\varphi(n)$ である。$\square$

$k\ge k'$ としてよい。$k=k'+\varphi(n)t$（$t\ge0$）と書けて、$a^k=a^{k'}\bigl(a^{\varphi(n)}\bigr)^t\equiv a^{k'}\pmod n$ である。$\square$