合同式とは
合同式とは、$a,b$ を整数、$n$ を正の整数とすると、$a$ を $n$ で割った余りと、$b$ を $n$ で割った余りが等しいことを表す数式で、以下のように表記されます。
$$a\equiv b\pmod{n}$$
また、このことは $a$ と $b$ の差が $n$ で割り切れると言うこともできます。
$$a-b\equiv0\pmod{n}$$
尚、$b$ を $n$ で割った余りが $a$ であることは次のように表されます。この場合は、イコール（$=$）を使って表します。
$$a=b\pmod{n}$$
$n=7$ の場合で例を挙げると、以下のようになります。
| $(1,8)$の場合 | $(15,8)$の場合 |
| $1=8\pmod{7}$ $1\equiv8\pmod{7}$ |
$15\ne8\pmod{7}$ $15\equiv8\pmod{7}$ |
合同式の性質
合同式には次のような性質があります。
| $a_1\equiv b_1\pmod{n}$ かつ $a_2\equiv b_2\pmod{n}$ ならば $a_1+a_2\equiv b_1+b_2\pmod{n}$ －① $a_1a_2\equiv b_1b_2\pmod{n}$ －② |
これらは以下のように証明できます。
$a_1$ と $b_1$、$a_2$ と $b_2$ 同じ余りをもつため、余りをそれぞれ $\delta_1$ と $\delta_2$ とすると、任意の $\alpha_i,\beta_i$ により以下のように書くことができます。
$$a_1=\alpha_1n+\delta_1 , b_1=\beta_1n+\delta_1$$
$$a_2=\alpha_2n+\delta_2 , b_2=\beta_2n+\delta_2$$
まず、①について、
$$a_1+a_2=(\alpha_1+\alpha_2)n+\delta_1+\delta_2$$
従って、
$$a_1+a_2\pmod{n}=\delta_1+\delta_2$$
同様に $b_1+b_2$ を計算すると以下の通り、①が成り立つことが分かります。
$$b_1+b_2\pmod{n}=\delta_1+\delta_2$$
次に、②について、
$$a_1a_2=\alpha_1\alpha_2n^2+(\alpha_1\delta_2+\alpha_2\delta_1)n+\delta_1\delta_2$$
従って、
$$a_1a_2\pmod{n}=\delta_1\delta_2$$
同様に $b_1b_2$ を計算すると以下の通り、②が成り立つことが分かります。
$$b_1b_2\pmod{n}=\delta_1\delta_2$$
| $a\equiv b\pmod{n}$ ならば任意の整数 $c$ と任意の正の整数 $m$ に対して $a+c\equiv a+c\pmod{n}$ －③ $ac\equiv bc\pmod{n}$ －④ $a^m\equiv b^m\pmod{n}$ －⑤ |
③④は①②と同様に証明することができます。⑤については、
$$a^m=(\alpha n+\delta)^m=\alpha^mn^m+\cdots+m\alpha\delta^{n-1}n+\delta^n$$
従って、
$$a^m\pmod{n}=\delta^n$$
同様に $b^m$ を計算すると以下の通り、⑤が成り立つことが分かります。
$$b^m\pmod{n}=\delta^n$$
| $a$ と $n$ が互いに素のとき、次式を満たす $x$ が存在する $ax\equiv 1\pmod{n}$ －⑥ |
拡張ユークリッド互除法より、整数 $a,n$ の最大公約数を $d$ とするとき、以下の式を満たす整数 $x,y$ 存在します。
$$ax+ny=d$$
このとき $a,n$ が互い素であれば、$ax+ny=1$ となり、⑥が成り立つことが分かります。
