同余是与$+$、$\times$相容的等价关系

自反性:$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}$上的运算。