どういう性質があるのでしょうか？
合同式とは、整数の余りの関係に着目した式です。
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$から出てくるためです。
Share:
