合同式とは？ 余りに着目した関係式

　合同式とはどういったものでしょうか？
どういう性質があるのでしょうか？

　合同式とは、整数の余りの関係に着目した式です。

2つの整数$A,B$をそれぞれ整数$n$で割ると

$$\begin{align*}A\div n&=a余りr\\[1em]B\div n&=b余りr\end{align*}$$

または、別の形で

$$\begin{align*}A&=an+r\\[1em]B&=bn+r\end{align*}$$

となるとき、どちらも余りが$r$で一致するので

$$A\equiv B\ (\text{mod}\ n)$$

と表すことができます。
読み方は「（$A$）合同（$B$）モッド（$n$）」や「（$n$）を法として（$A$）合同（$B$）」です。

　整数$A,B,C$をそれぞれ整数$n$で割って

$$\begin{align*}A&=an+r\tag1\\[1em]B&=bn+r\tag2\\[1em]C&=cn+r'\tag3\\ &ただしr\neq r',0<r<n,0<r'<n\end{align*}$$

であることをもちいると、合同式の性質は以下のようなものとなります。

整数と余り

　$(1)$が成り立つとき、合同式で

$$A\equiv r\ (\text{mod}\ n)$$

が成り立ちます。

これは$r$を$n$で割ると

$$r=0\cdot n+r$$

のように商が$0$で$r$がそのまま余りとなるためです。

負の余り

　$(1)$が成り立つとき、合同式で

$$A\equiv r-n\ (\text{mod}\ n)$$

が成り立ちます。

これは$(1)$を変形すると

$$\begin{align*}A&=\{(a+1)-1\}n+r\\[0.5em]&=(a+1)n-n+r\\[0.5em]&=(a+1)n+(r-n)\end{align*}$$

となるためです。

　さらに拡張すると整数$k$をもちいて

$$A\equiv r-kn\ (\text{mod}\ n)$$

が成り立ちます。

これは同様に$(1)$を変形して

$$\begin{align*}A&=\{(a+k)-k\}n+r\\[0.5em]&=(a+k)n-kn+r\\[0.5em]&=(a+1)n+(r-kn)\end{align*}$$

となるためです。

このことから2つの整数$A,B$の間に$A\equiv B\ (\text{mod}\ n)$が成り立つとき$B$には$B=r-kn$を満たす整数$k$が存在することがわかります。

和と差

　2つの整数$A,B$の間に

$$A\equiv B\ (\text{mod}\ n)$$

が成り立つとき整数$C$をもちいて

$$A\pm C\equiv B\pm C\ (\text{mod}\ n)$$

が成り立ちます。

これは$(1)$と$(3)$の辺々を足して（引いて）

$$\begin{align*}A\pm C&=(an+r)\pm(cn+r')\\[0.5em]&=(an\pm cn)+(r\pm r')\\[0.5em]&=(a\pm c)n+(r\pm r')\tag{複号同順}\end{align*}$$

$(2)$と$(3)$の辺々を足して（引いて）

$$\begin{align*}B\pm C&=(bn+r)\pm(cn+r')\\[0.5em]&=(bn\pm cn)+(r\pm r')\\[0.5em]&=(b\pm c)n+(r\pm r')\tag{複号同順}\end{align*}$$

となり、余りがどちらも$r\pm r'$となるためです。

積

　2つの整数$A,B$の間に

$$A\equiv B\ (\text{mod}\ n)$$

が成り立つとき、整数$C$をもちいて

$$AC\equiv BC\ (\text{mod}\ n)$$

が成り立ちます。

これは$(1)$と$(3)$の辺々を掛けて

$$\begin{align*}AC&=(an+r)(cn+r')\\[0.5em]&=acn^2+(ar'+cr)n+rr'\\[0.5em]&=(acn+ar'+cr)n+rr'\end{align*}$$

$(2)$と$(3)$の辺々を掛けて

$$\begin{align*}BC&=(bn+r)(cn+r')\\[0.5em]&=bcn^2+(br'+cr)n+rr'\\[0.5em]&=(bcn+br'+cr)n+rr'\end{align*}$$

となり、余りはどちらも$rr'$から出てくるためです。

累乗

　2つの整数$A,B$の間に

$$A\equiv B\ (\text{mod}\ n)$$

が成り立つとき、整数$k$をもちいて

$$A^k\equiv B^k\ (\text{mod}\ n)$$

が成り立ちます。

これは$(1)$の両辺を$k$乗して、二項定理より

$$\begin{align*}A^k&=(an+r)^k\\[0.5em]&=(an)^k+k(an)^{k-1}r+{_kC_2}(an)^{k-2}r^2+\cdots\\ &\quad+{_kC_{k-2}}(an)^2r^{k-2}+kanr^{k-1}+r^k\\[0.5em]&=\left(a^kn^{k-1}+ka^{k-1}n^{k-2}r+\cdots\right.\\ &\quad\left.+{_kC_{k-2}}a^2nr^{k-2}+kar^{k-1}\right)n+r^k\end{align*}$$

同様に$(2)$の両辺を$k$乗して、

$$\begin{align*}B^k&=(bn+r)^k\\[0.5em]&=(bn)^k+k(bn)^{k-1}r+{_kC_2}(bn)^{k-2}r^2+\cdots\\ &\quad+{_kC_{k-2}}(bn)^2r^{k-2}+kbnr^{k-1}+r^k\\[0.5em]&=\left(b^kn^{k-1}+kb^{k-1}n^{k-2}r+\cdots\right.\\ &\quad\left.+{_kC_{k-2}}b^2nr^{k-2}+kbr^{k-1}\right)n+r^k\end{align*}$$

となり、余りはどちらも$r^k$から出てくるためです。