整数の合同演算・完全剰余系

整数の合同と不合同
1. 同値関係（反射率、対称律、推移律）
剰余類
完全剰余系
1. 合同式の加算と減算
合同式の乗算とべき乗
1. 合同式のべき乗

整数の合同と不合同

1 に 7 を加えながら数字を並べてみます。
\[1,\:8,\:15,\:22,\:29,\:36,\:43,\:50,\:\cdots\]
並べた数字はいずれも 7 で割ると 1 余ります。そこで、これらは同じ種類の数であると考えて $\equiv$ という記号で結ぶことにします。
\[1\equiv 8\equiv 15\equiv 22\equiv 29\equiv 36\equiv 43\equiv 50\equiv \cdots\quad (\mathrm{mod}\;7)\]
このように $\equiv$ で結ばれた数を「 7 を法として合同である」といいます。$\mathrm{mod}\;7$ は 7 を法とすることを明示する記号です。しかしたとえば 18 という数は上のグループに含まれていないので (7 で割ると 4 余ります) 、
\[18\not\equiv 29\quad (\mathrm{mod}\;7)\]
のように書いて、18 と 29 は「 7 を法として不合同である」といいます。一般に整数 $a,\:b$ をそれぞれ $m$ で割ったときに余りが等しければ、$a$ と $b$ は $m$ を法 (modulus) として合同 (congruent) である といい、
\[a\equiv b\quad (\mathrm{mod}\;m)\]
と書きます。ここで $a,\:b$ はそれぞれ整数 $s,\:t,\:r$ を用いて
\[a=ms+r,\quad b=mt+r\]
のように書くことができます。$r$ は $a,\:b$ を $m$ で割ったときの余りです。すると
\[a-b=m(s-t)\]
となるので、$a-b$ は $m$ で割り切れます。逆に $a-b$ は $m$ で割り切れるのなら、
\[a-b=mk\]
なので、
\[b=mq+r,\:\: a=m(k+q)+r\quad (0\leq r\lt m)\]
となって、$a,\:b$ を $m$ で割ったときの余りは等しくなります。これを用いて合同の定義をまとめると次のようになります。

【定義C1】$a,\:b$ を整数、$m$ を自然数とする。
$a-b$ が $m$ で割り切れるとき、$a$ と $b$ は法 $m$ について合同であるといい、
\[a\equiv b\quad (\mathrm{mod}\;m)\]と表す。$a-b$ が $m$ で割り切れないとき、$a$ と $b$ は法 $m$ について不合同であるといい、
\[a\not\equiv b\quad (\mathrm{mod}\;m)\]と表す。

記号を使って手短に書くと次のようになります。

【定義C1】$a,\:b\in\mathbb{Z},\quad m\in\mathbb{N}$
$\qquad a\equiv b\quad (\mathrm{mod}\;m)\quad\Longleftrightarrow\quad m\:|\:a-b$
$\qquad a\not\equiv b\quad (\mathrm{mod}\;m)\quad\Longleftrightarrow\quad m\mid \hspace{-.67em}/\:a-b$

具体例を載せておくので、実際に $a-b$ が $m$ で割り切れるか確認してみてください。
\[\begin{align*}&11\equiv 19\quad (\mathrm{mod}\;2)\\[6pt]&7\equiv 32\quad (\mathrm{mod}\;5)\\[6pt]&130\equiv 200\quad (\mathrm{mod}\;10)\\[6pt]\end{align*}\]

同値関係（反射率、対称律、推移律）

今までの数学で用いてきた等号について、次のような関係が成り立つことは暗黙の了解としてきたはずです（普段は意識することもないと思います）。

① 反射律　$a=a$
② 対称律　$a=b$　ならば　$b=a$
③ 推移律　$a=b,\:b=c$　ならば　$a=c$

ある集合の２元同士の関係 R が上の条件を全て満たせば同値関係（equivalence relation）にあるといいます。もちろん関係の種類によっては ① ～ ③ のいずれかを満たさない場合もあります。たとえば自然数 $b$ が自然数 $a$ で割り切れる、すなわち $a\:|\:b$ という関係を考えたときに上の３つの条件を順にチェックしていくと

① 反射律　$a\equiv a\quad (\mathrm{mod}\;m)$
② 対称律　$a\equiv b\quad (\mathrm{mod}\;m)$　ならば　$b\equiv a\quad (\mathrm{mod}\;m)$
③ 推移律　$a\equiv b,\:b=c\quad (\mathrm{mod}\;m)$　ならば　$a\equiv c\quad (\mathrm{mod}\;m)$

【① 反射律の証明】
$\qquad m\:|\:a-a\quad (\mathrm{mod}\;m)$　なので　$a\equiv a\quad (\mathrm{mod}\;m)$

【② 対称律の証明】
$\qquad m\:|\:a-b\quad (\mathrm{mod}\;m)$ より
$\qquad m\:|\:-(a-b)\quad (\mathrm{mod}\;m)$
$\qquad m\:|\:b-a\quad (\mathrm{mod}\;m)$
$\qquad \therefore b\equiv a\quad (\mathrm{mod}\;m)$

【③ 推移律の証明】
$\qquad a\equiv b\quad (\mathrm{mod}\;m)$　なので　$b=a+sm$
$\qquad b\equiv c\quad (\mathrm{mod}\;m)$　なので　$c=b+tm$
$\qquad c=a+(s+t)m\quad\therefore a\equiv c\quad (\mathrm{mod}\;m)$

ちなみに「合同」と聞けば小学校の時に習った「三角形の合同」を思い浮かべるかたも多いと思いますが、実は「三角形の合同」も同値関係にあります。ぜひ確認してみてください。

剰余類

任意の整数を 7 で割ると、余りは 0, 1, 2, 3, 4, 5, 6 のいずれかになります。そこで、その余りの数によって整数を 7 つの集合に分けてみます。

\[\begin{align*}&C_0\,\{\:\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\:\}\\[6pt]&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
それぞれの集合内の要素同士は法 7 のもとで合同です。このように互いに合同な整数の集合を剰余類（residue class）とよびます。$C$ は Class の頭文字です。

[定義 C2] 整数全体の集合 $\mathbb{Z}$ を自然数 $m$ で割ったときの剰余
\[0,\:1,\:2,\:\cdots,\:m-1\]によって分類し、剰余が $r$ である数の集合を $C_r$ で表すと　
\[C_0,\:C_1,\:C_2,\:\cdots,\:C_{m-1}\]という $m$ 個の類（剰余類）ができます。$C_r$ に属する全ての要素は
\[mt+r\:\:(t\in\mathbb{Z})\]と表すことができます。

法 7 による剰余類の例を見れば、どの整数も必ずどこかの剰余類に属し、また複数の剰余類に属することはないことは、ほぼ自明であるように思えますが、これについても一般的に証明しておきます。証明には上で絵説明した同値関係を用います。

【定理C1】
① どの整数も必ずどこかの剰余類に属します。
② どの整数も複数の剰余類に属することはありません。すなわち
\[r\neq s\quad\Longrightarrow\quad C_r\cap C_s=\phi\]

　ここで $\phi$ は空集合を表す記号で、上の定理は $r\neq s$ のときは $C_r$ かつ $C_s$ を満たす要素は存在しないことを述べています。

【定理C1 の証明】

① 反射律 $a\equiv a\:(\mathrm{mod}\;m)$ より $a\in C_a$ です。
　すなわち、どの整数も必ずどこかの剰余類に属します。

② $C_a$ と $C_b$ のどちらにも属する整数 $x$ が存在すると仮定すると

$a\in C_a,\:\:x\in C_a$　なので　$a\equiv x\:(\mathrm{mod}\;m)$
$b\in C_b,\:\:x\in C_b$　なので　$b\equiv x\:(\mathrm{mod}\;m)$

　推移律によって
　
\[a\equiv x,\:\:x\equiv b\:(\mathrm{mod}\;m)\]
であるならば $a\equiv b\:(\mathrm{mod}\;m)$ が成立します。つまり $C_a=C_b$ となって 2 つの類は完全に一致してしまいます。したがって、どの整数も複数の剰余類に属することはありません。

完全剰余系

　先ほどの法 7 による剰余類を再掲します。
　
\[\begin{align*}&C_0\,\{\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\}\\[6pt]&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
　それぞれの剰余類から 1 つずつ値を取り出して、
　
\[\{14,\:8,\:-5,\:10,\:-2,\:19,\:27\}\]
という集合を作ってみます。当然のことながら、この集合には 7 で割ったときの余りの相異なる数が過不足なく含まれています。このような集合のことを 完全剰余系 とよびます。別にどのような値をとってきても完全剰余系であることに変わりはないのですが、たとえば
　
\[\{0,\:1,\:2,\:3,\:4,\:5,\:6\}\]
のように選ぶと、法 7 による完全剰余系であることが一目瞭然です。一般的な定義も載せておきます。

[定義 C3] 法 $m$ による剰余類
\[C_1,\:C_2,\:\cdots,\:C_{m-1}\]の中から 1 つずつ値（類の代表）を取り出して集めた数の組を完全剰余系とよびます。

合同式の加算と減算

　法 7 による剰余類を再掲します。
　
\[\begin{align*}&C_0\,\{\:\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\:\}\\[6pt]&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
　ここで、たとえば $C_2$ から $2$, $C_3$ から $17$ という要素を抜き出して足し合わせてみると
　
\[2+17=19\in C_5\]
となっています ($19$ は $7$ で割ると $5$ 余ります) 。また $C_2$ から $-5$, $C_3$ から $10$ という要素を抜き出して足し合わせてみても
　
\[-5+10=5\in C_5\]
となります。同じように $C_2,\:C_3$ からどのような数を抜き出して足し合わせてみても、それは必ず C_5 類の要素となります。一般に加算については、法 $m$ による剰余類 $C_a,\:C_b$ を
　
\[\begin{align*}&C_a\,\{\:a_1,\:a_2,\:a_3,\:\cdots\:a_i,\:\cdots\:\}\\[6pt]
&C_b\,\{\:b_1,\:b_2,\:b_3,\:\cdots\:b_i,\:\cdots\:\}\\[6pt]\end{align*}\]
としたときに、$C_a,\:C_b$ から任意の要素
　
\[a_i\in C_a,\quad b_i\in C_b\]
を取り出してきて足し合わせると必ず同じ剰余類 $C_x$ の要素となります。
　
\[a_i+b_i\in C_x\]
　これは言い換えると $C_a,\:C_b$ からどのような数を抜き出して足し合わせても合同になるということです。

[定理 C2] $a_1\equiv a_2,\:\:b_1\equiv b_2\:(\mathrm{mod}\;m)$ ならば、
\[\begin{align*}(1)&\:a_1+b_1\equiv a_2+b_2\:(\mathrm{mod}\;m)\\[6pt]
(2)&\:a_1-b_1\equiv a_2-b_2\:(\mathrm{mod}\;m)\end{align*}\]が成り立ちます。

【定理C2 の証明】
(1) $a_2=a_1+ms,\:\:b_2=b_1+mt\:(s,t\in\mathbb{Z})$ と書けるので、
　
\[a_2+b_2=a_1+b_1+m(s+t)\equiv a_1+b_1\:(\mathrm{mod}\;m)\]
となります。(2) も同じように証明できます。（証明終）

　この定理は合同式においても普通の等式と同じように辺々を足し合せてもかまわないということです。具体的な計算例を載せておきます。たとえば法 5 のもとで
　
\[28\equiv 53,\quad 36\equiv 51\:(\mathrm{mod}\;m)\]
という合同式が成り立っているので、両辺を足し合わせて
　
\[64\equiv 104\equiv 4\:(\mathrm{mod}\;m)\]
という合同式も成り立ちます。

合同式の乗算とべき乗

　再び法 $7$ による剰余類を並べてみます。
　
\[\begin{align*}&C_0\,\{\:\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\:\}\\[6pt]&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
　たとえば $C_2$ から $16$, $C_3$ から $3$ という要素を抜き出して掛け合わせてみると
　
\[16\times 3=48\in C_6\]
となります。あるいは $C_2$ から $9$, $C_3$ から $10$ という要素を抜き出して乗じてみても
　
\[9\times 10=90\in C_6\]
となります。これは決して偶然ではなく、$C_2,\:C_3$ からどのような数を抜き出して掛け合わせても必ず $C_6$ の要素となります。一般に法 $m$ のもとで $C_a,\:C_b$ から適当な数を抜き出して掛け合わせると、それらの数は全て合同となります（同じ類の元となります）。

[定理 C3] $a_1\equiv a_2,\:\:b_1\equiv b_2\:(\mathrm{mod}\;m)$ ならば、
\[a_1\,b_1\equiv a_2\,b_2\:(\mathrm{mod}\;m)\]

【定理C3 の証明】
　$a_2=a_1+ms,\:\:b_2=b_1+mt\:(s,t\in\mathbb{Z})$ と書けるので、
　
\[\begin{align*}a_1\,b_1&=(a_1+ms)(b_1+mt)\\[6pt]&=a_1\,b_1+m(a_1\,t+b_1\,s+st)\equiv a_1\,b_1\:(\mathrm{mod}\;m)\end{align*}\]
となります。（証明終）

　加算の時と同じように、乗算においても普通の (“=” で結ばれた) 等式のように、（法 $m$ が共通していれば）辺々を掛け合わせることが許されるということです。たとえば
　
\[13\equiv 22,\quad 8\equiv 17\:(\mathrm{mod}\;m)\]
が成立しているので、辺々を掛けると左辺と右辺はそれぞれ
　
\[\begin{align*}13\times 8=104\equiv 2\:(\mathrm{mod}\;m)\\[6pt]22\times 17=374\equiv 2\:(\mathrm{mod}\;m)\end{align*}\]
となって合同であることがわかります。

合同式のべき乗

　法 7 による剰余類 $C_2$ を再掲します。
　
\[C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\]
　$C_2$ から $2$ と $-5$ を取り出して、それぞれ 2 乗すると $4,\:25$ となり、それぞれ $7$ で割ると $4$ が余るので $C_4$ の元となります。
　
\[4,\:25\in C_4\]
また、$2$ と $-5$ をそれぞれ 3 乗すると
　
\[8,\:-125\in C_1\]
となって、やはり 2 数は同じ類の元となります。このように、ある剰余類から 2 数を取り出してべき乗すると、それぞれ一緒に同じ類に移ります（合同関係が維持されます）。

[定理 C4] $a_1\equiv a_2\:(\mathrm{mod}\;m)$ ならば、
\[a_1^n\,\equiv\,a_2^n\:(\mathrm{mod}\;m)\quad n\in\mathbb{N}\]

　ここで $\mathbb{N}$ は自然数の集合を表しています。

【定理C4 の証明】数学的帰納法を用いて証明します。$n=1$ のとき
　
\[a_1\equiv a_2\:(\mathrm{mod}\;m)\]
が成り立っています。$n=k-1$ のとき
　
\[a_1\,^{k-1}\equiv a_2\,^{k-1}\:(\mathrm{mod}\;m)\]
が成り立つことを仮定すると、定理 C3（合同式の乗算）より
　
\[a_1\,^{k-1}\,a_1\,\equiv a_2\,^{k-1}\,a_2\:(\mathrm{mod}\;m)\]
　すなわち
　
\[a_1^k\,\equiv\,a_2^k\:(\mathrm{mod}\;m)\]
が成り立ちます。よって任意の自然数 $n$ について
　
\[a_1^n\,\equiv\,a_2^n\:(\mathrm{mod}\;m)\quad n\in\mathbb{N}\]
が成り立ちます。（証明終）
　
　たとえば $3\equiv 7\:(\mathrm{mod}\;4)$ が成り立っているので、両辺を 2 乗、3 乗, … していっても合同関係は維持されるということです。
　
\[\begin{align*}3^2\equiv 7^2\:(\mathrm{mod}\;4)\\[6pt]3^3\equiv 7^3\:(\mathrm{mod}\;4)\\[6pt]3^4\equiv 7^4\:(\mathrm{mod}\;4)\\[6pt]\cdots\cdots\cdots\cdots\cdots\end{align*}\]
　本当に成り立っているかどうか気になる場合は、Excel の MOD 関数などで実際に計算させて確認してください。