簡約法則と法での逆元の存在

$\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$である——互いに素という仮定を外すと簡約は実際に失敗する。