消去律与模逆元的存在性

由$\gcd(c,m)=1$,贝祖等式(欧几里得算法的推论)保证$\exists\, u,v \in \mathbb{Z}:\ cu+mv=1$:存在整数$u,v$使$cu+mv=1$。

将$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$——一旦去掉互素假设,消去律确实会失效。