オイラーの定理

法$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)$を割り切る。