合同式とは

/代数学

合同式とは

合同式とは、$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$ となり、⑥が成り立つことが分かります。

 

数学
解析学、代数学、幾何学、統計分析、数学基礎、物理数学
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

タイトルとURLをコピーしました