【定理・公式・証明】高校数学定理・公式 – 数学A – 合同式

[Ⅰ] $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 \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$ において，(※)は成り立つ。