合同は$+$と$\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)により合同は同値関係となり、最後の2ステップは$\mathbb{Z}$上のすべての環演算が剰余類$\mathbb{Z}/m\mathbb{Z}$上のwell-definedな演算へと降りることを示している。