合同式とは
合同式とは、整数 $a$ 、$b$ が合同であることを表す式で、正の整数 $n$ に対して以下のように表すことができます。
$$b\equiv a\pmod{n} -①$$
①が成り立つとき、以下のように言い表すことができます。これらは合同式の定義となります。
- $a$ を $n$ で割った余りと、$b$ を $n$ で割った余りは等しい。
- $b-a$ は $n$ で割り切れる。
- 整数 $k$ により $b=a+kn$ で表される。
また、定義より以下の関係が成り立つことが分かります。
- 反射律：$a\equiv a\pmod{n}$
- 対称律：$a\equiv b\pmod{n}$ ならば $b\equiv a\pmod{n}$
- 推移律：$a\equiv b\pmod{n}$ かつ $b\equiv c\pmod{n}$ ならば $a\equiv c\pmod{n}$
剰余類と既約剰余類
①の関係が成り立つとき、$b$ は $a$ の $\pmod{n}$ での剰余類と呼びます。$a=3$ 、$n=7$ とすると、剰余類の集合は以下で表されます。
$3\pm 7k=$｛$\cdots$、$-18$ 、$-11$ 、$-4$ 、$3$ 、$10$ 、$17$ 、$24$ 、$\cdots$｝
また、以下の関係が成り立つ場合は、$b$ は $a$ の $\pmod{n}$ での既約剰余類と呼びます。上の例は既約剰余類となっています。
$$\mathrm{gcd}(a,n)=1$$
原始根と位数
整数 $a$ と $n$ について、以下の関係が成り立つとき、$a$ を $\pmod{n}$ に対する原始根、$n-1$ を $a$ の位数と呼びます。
$$a\pmod{n}\ne1$$$$a^2\pmod{n}\ne1$$$$\cdots$$$$a^{n-2}\pmod{n}\ne1$$$$a^{n-1}\pmod{n}=1$$
合同式の性質
- $a\equiv b\pmod{n}$ かつ $c\equiv d\pmod{n}$ ならば以下が成り立つ。
$a+c\equiv b+d\pmod{n}$ －②（導出）
$ac\equiv bd\pmod{n}$ －③（導出）
- $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$ と $n$ が互いに素のとき、次式を満たす $x$ が存在する。（導出）
$ax\equiv 1\pmod{n}$ －⑦
②を導く
$a$ と $b$、$c$ と $d$ 同じ余りをもつため、余りをそれぞれ $\alpha$ と $\beta$ とすると、任意の $A\sim D$ により以下のように書くことができます。
$$a=An+\alpha , b=Bn+\alpha -(1)$$$$c=Cn+\beta , d=Dn+\beta -(2)$$
これらを②の左辺に代入すると、
$$a+c=(A+C)n+\alpha+\beta$$
従って、
$$a+c\pmod{n}\equiv\alpha+\beta$$
同様に②の右辺を計算すると以下の通り、②が成り立つことが分かります。
$$b+d\pmod{n}\equiv\alpha+\beta$$
③を導く
(1)と(2)を③の左辺に代入すると、
$$ac=ACn^2+(A\beta+C\alpha)n+\alpha\beta$$
従って、
$$ac\pmod{n}=\alpha\beta$$
同様に $bd$ を計算すると以下の通り、③が成り立つことが分かります。
$$bd\pmod{n}=\alpha\beta$$
⑥を導く
(1)を⑥の左辺に代入すると、
$$a^m=(An+\alpha)^m=A^mn^m+\cdots+mA\alpha^{m-1}n+\alpha^m$$
従って、
$$a^m\pmod{n}=\alpha^m$$
同様に $b^m$ を計算すると以下の通り、⑥が成り立つことが分かります。
$$b^m\pmod{n}=\alpha^m$$
⑦を導く
拡張ユークリッド互除法より、整数 $a,n$ の最大公約数を $d$ とするとき、以下の式を満たす整数 $x,y$ 存在します。
$$ax+ny=d$$
このとき $a,n$ が互い素であれば、$ax+ny=1$ となり、⑦が成り立つことが分かります。
