合同式とその基本的な性質

例

\(8-5=3\)は\(3\)の倍数なので, \(8 \equiv 5 \pmod 3\)である。
\(8\)と\(5\)は\(3\)を法として合同である。

\(21-13=8\)は\(4\)の倍数なので, \(21 \equiv 13 \pmod 4\)である。
\(21\)と\(13\)は\(4\)を法として合同である。

\(16-(-2)=18\)は\(3\)の倍数なので, \(16 \equiv -2 \pmod 3\)である。
\(16\)と\(-2\)は\(3\)を法として合同である。

（合同式の中に登場する整数は負でもかまいません。）

例

\(5\)を\(4\)で割った余りは\(1\)なので, \(5 \equiv 1 \pmod 4\)である。

\(18\)を\(5\)で割った余りは\(3\)なので, \(18 \equiv 3 \pmod 5\)である。

証明

\(a \equiv b \pmod m\), \(c \equiv d \pmod m\)より\(a-b=mk\), \(c-d=ml\)となる整数\(k, l\)が存在する。
$$
\begin{aligned}
&(a+c)-(b+d) \\
&=(a-b)+(c-d) \\
&=mk+ml \\
&=m(k+l)
\end{aligned}
$$
であり, \(k+l\)は整数なので, \((a+c)-(b+d)\)は\(m\)の倍数である。

したがって, \(a+c \equiv b+d \pmod m\)

証明

上と同様に、\(a \equiv b \pmod m\), \(c \equiv d \pmod m\)より\(a-b=mk\), \(c-d=ml\)となる整数\(k, l\)が存在する。
$$
\begin{aligned}
&(a-c)-(b-d) \\
&=(a-b)-(c-d) \\
&=mk-ml \\
&=m(k-l)
\end{aligned}
$$
であり, \(k-l\)は整数なので, \((a-c)-(b-d)\)は\(m\)の倍数である。

したがって,\(a-c \equiv b-d \pmod m\)

証明

\(a \equiv b \pmod m\), \(c \equiv d \pmod m\)より\(a-b=mk\), \(c-d=ml\)となる整数\(k, l\)が存在する。
$$
\begin{aligned}
&ac-bd \\
&=ac-ad+ad-bd \\
&=a(c-d)+d(a-b) \\
&=aml+dmk \\
&=m(al+dk)
\end{aligned}
$$
であり, \(al+dk\)は整数なので, \(ac-bd\)は\(m\)の倍数である。

したがって, \(ac \equiv bd \pmod m\)

証明

数学的帰納法により示す。
\(k\)を自然数とする。

[1]\(n=1\)のとき
\(a^1=a \equiv b=b^1 \pmod m\)より合同式は成り立つ。

[2]\(n=k\)のとき合同式が成り立つと仮定する。
\(a \equiv b \pmod m\)かつ\(a^k \equiv b^k \pmod m\)であるので, 合同式の性質より\(a \cdot a^k \equiv b \cdot b^k\)
すなわち\(a^{k+1} \equiv b^{k+1} \pmod m\)
よって\(n=k+1\)のときにも合同式は成り立つ。