合同式と合同算術(モジュラー演算)

これにより合同式は算術として使えるようになる:巨大な元の数の代わりに余り同士を直接加減乗算しても、常に正しい余りが得られるということである——コンピュータが$16$桁のカード番号を検証したり、$100$桁の数を一度も保存せずに$7^{100} \bmod 13$を計算できたりする理由はここにある。

反射性:$a-a=0$であり、任意の$m$に対して$m\mid 0$なので、$a\equiv a\pmod m$。

対称性:$a\equiv b\pmod m$ならば、ある整数$k$について$a-b=mk$であり、よって$b-a=m(-k)$。$-k$も整数なので$m\mid(b-a)$、すなわち$b\equiv a\pmod m$。

推移性:$a\equiv b\pmod m$かつ$b\equiv c\pmod m$ならば、$a-b=mk_1$、$b-c=mk_2$と書ける。両式を足すと$a-c=(a-b)+(b-c)=m(k_1+k_2)$となり、$m\mid(a-c)$、すなわち$a\equiv c\pmod m$。

加法との両立性:$a-b=mk_1$と$c-d=mk_2$から両式を足すと$(a+c)-(b+d) = m(k_1+k_2)$となり、これは$m$の倍数なので$a+c\equiv b+d\pmod m$。

乗法との両立性:$ac-bd = ac-bc+bc-bd = c(a-b)+b(c-d) = c\cdot mk_1 + b\cdot mk_2 = m(ck_1+bk_2)$と書ける。これも$m$の倍数なので$ac\equiv bd\pmod m$。(i)-(iii)により合同は同値関係となり、最後の2ステップは$\mathbb{Z}$上のすべての環演算が剰余類$\mathbb{Z}/m\mathbb{Z}$上のwell-definedな演算へと降りることを示している。

通常の「割り算」は実際には逆元による乗算であり、この定理はその逆元が法$m$に関していつ存在するかをまさに教えてくれる:$c$が$m$と共通の因数を持たないときちょうど存在する。この条件がなければ簡約は実際に失敗する(上の表の最終行を参照)。だからこそ、法$m$に関するべき乗についての後続のすべての結果——フェルマーの小定理、オイラーの定理、中国剰余定理——はこのただ一つの代数的事実の上に築かれている。

$\gcd(c,m)=1$より、ベズーの等式(ユークリッドの互除法の帰結)により$\exists\, u,v \in \mathbb{Z}:\ cu+mv=1$が保証される:$cu+mv=1$を満たす整数$u,v$が存在する。

$ac\equiv bc\pmod m$の両辺に$u$を掛ける:$acu\equiv bcu\pmod m$。ここで$cu=1-mv$を代入すると、左辺は$a(1-mv)=a-amv$となり、$amv$は$m$の倍数なので$a(1-mv)\equiv a\pmod m$;同様に右辺も$b(1-mv)\equiv b\pmod m$。したがって$a\equiv b\pmod m$となり、簡約法則が証明される。

さらに、$a=1,b=0,c=c$とする必要はない——直接、同じ代入により$cu = 1-mv \equiv 1 \pmod m$なので、$u$自体が$c$の法$m$に関する乗法逆元である:これはまさに定理の主張が存在を述べている対象である。

仮定$\gcd(c,m)=1$は本質的である:$c=4,\ m=6$とすると($\gcd(4,6)=2\neq1$)、$4\times 2=8\equiv 2\pmod 6$かつ$4\times 5=20\equiv 2\pmod 6$なので$4\times2\equiv 4\times5\pmod 6$だが、$2\not\equiv 5\pmod 6$である——互いに素という仮定を外すと簡約は実際に失敗する。