合同式
[Ⅰ] $a \equiv a( \mathrm{ mod } \ m)$
[Ⅱ] $a \equiv b ( \mathrm{ mod } \ m) $ ならば， $b \equiv a( \mathrm{ mod } \ m)$
[Ⅲ] $a \equiv b( \mathrm{ mod } \ m)$ ， $b \equiv c( \mathrm{ mod } \ m)$ ならば， $a \equiv c( \mathrm{ mod } \ m)$
[Ⅰ] $a-a=0=(m の倍数)$
であるから，
$a \equiv a( \mathrm{ mod } \ m)$
[Ⅱ] $a \equiv b( \mathrm{ mod } \ m)$ より，
$a-b=mk$ ( $k$ は整数)
このとき，
$b-a=m \cdot (-k) =(mの倍数)$
であるから，
$b \equiv a ( \mathrm{ mod } \ m)$
[Ⅲ] $a \equiv b ( \mathrm{ mod } \ m),b \equiv c ( \mathrm{ mod } \ m)$ より，
$\begin{eqnarray} \left \{ \begin{array}{l} a-b=mk \\ b-c=ml \end{array} \right. \end{eqnarray}$ ( $k,l$ は整数)
2式の和をとり，
$a-c=m(k+l)=(m の倍数)$
よって，
$a \equiv c ( \mathrm{ mod } \ m)$
合同式の性質
[Ⅰ] $a+c \equiv b+d( \mathrm{ mod } \ m)$
[Ⅱ] $a-c \equiv b-d( \mathrm{ mod } \ m)$
[Ⅲ] $ac \equiv bd ( \mathrm{ mod } \ m)$
[Ⅳ] $a^n \equiv b^n ( \mathrm{ mod } \ m)$ ( $n$ は正の整数)
$a \equiv b ( \mathrm{ mod } \ m)$ ， $c \equiv d( \mathrm{ mod } \ m)$ より， $a-b=mk$ ， $c-d=ml$ であるから，
$a=ml+b$ ， $c=ml+d$ ( $k,l$ は整数)
[Ⅰ] $(a-c)-(b-d)=(mk+b+ml+d)-(b+d)=m(k+l)=(m の倍数)$ であるから， $a+c \equiv b+d( \mathrm{ mod } \ m)$ である。
[Ⅱ] $(a-c)-(b-d)= \{ mk+b-(ml+d) \} -(b-d)=m(k-l)= (m の倍数)$ であるから， $a-c \equiv b-d( \mathrm{ mod } \ m)$ である。
[Ⅲ] $ac-bd=(mk+b)(ml+d)-bd=m(mkl+dk+bl)=(m の倍数)$ であるから， $ac \equiv bd( \mathrm{ mod } \ m)$ である。
[Ⅳ] $a^n \equiv b^n ( \mathrm{ mod } \ m)$ ( $n$ は正の整数)
が成り立つことを，数学的帰納法で証明する。
(i) $n=1$ のとき， $a \equiv b( \mathrm{ mod } \ m)$ より，(※)は成立。
(ii) $n=k$ のとき，(※)が成り立つこと，すなわち $a^k \equiv b^k( \mathrm{ mod } \ m)$ を仮定する。
これと $a \equiv b( \mathrm{ mod } \ m$ より，[Ⅲ]から，
$a^k \cdot a \equiv b^k \cdot b( \mathrm{ mod } \ m)$ すなわち $a^{k+1} \equiv b^{k+1}( \mathrm{ mod } \ m)$
したがって， $n=k+1$ のときも(※)は成り立つ。
以上，(i)，(ii)より，すべての正の整数 $n$ において，(※)は成り立つ。