同余与模运算

这正是同余能当作算术来使用的原因:意味着我们可以直接对余数进行加、减、乘,而不必用原来巨大的数字,并且总能得到正确的余数——这也是计算机能够校验$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)使同余成为等价关系,最后两步表明$\mathbb{Z}$上的每个环运算都能良好地降到剩余类$\mathbb{Z}/m\mathbb{Z}$上的运算。

通常的"除法"本质上是乘以逆元,而这个定理恰好告诉我们该逆元何时在模$m$下存在:当且仅当$c$与$m$没有公因数时存在。若不满足此条件,消去律确实会失效(见上表最后一行),这正是后续所有关于模$m$幂次的结果——费马小定理、欧拉定理、中国剩余定理——都建立在这一条代数事实之上的原因。

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