合同式の計算規則
概要
合同式の計算規則（rules of congruence arithmetic）とは、正の整数 $n$ を法とする合同式 $a\equiv b\pmod n$（差 $a-b$ が $n$ で割り切れること）について、和・差・積・累乗の余りが、もとの数の余りだけで決まるという規則である。$a\equiv a'$、$b\equiv b'$ ならば $a\pm b\equiv a'\pm b'$、$ab\equiv a'b'$、$a^k\equiv a'^k$（$k$ は正の整数）であり、整数係数の多項式 $f$ について $a\equiv b$ ならば $f(a)\equiv f(b)$ である。このため大きな数の余りを小さな数で計算でき、余りで場合分けすれば無限個の整数についての主張を有限個の確認で示せる。一方、指数を法 $n$ で置き換えることや、両辺を同じ数で割ることは一般にはできない。
高校での出発点：余りだけで計算する
「今日は月曜日。100 日後は何曜日か」という問題は、100 を 7 で割った余りだけを見れば解ける。この記事では、このように 余りだけで計算してよい理由 を、一行ずつ証明する。まず、高校でよく見る計算を 3 つ並べる。
今日が月曜日だとする。7 日たつと同じ曜日に戻る。100 を 7 で割ると
$$
100=7\cdot14+2
$$
なので、100 日後は「98 日後（月曜日）のさらに 2 日後」であり、水曜日である。曜日は、日数を 7 で割った余りだけで決まる。
$2^3=8=7\cdot1+1$ なので、$2^3$ を $7$ で割った余りは $1$ である。$100=3\cdot33+1$ だから
$$
2^{100}=\left(2^3\right)^{33}\cdot2
$$
と書ける。ここで記号を 1 つ約束する。$A\equiv B\pmod 7$ は「$A$ と $B$ は $7$ で割った余りが等しい」と読む（正確な定義は def-cgrr-congruence で述べる）。「$2^3$ を余りの $1$ に置き換えてよい」とすると、
$$
2^{100}\equiv1^{33}\cdot2=2\pmod 7
$$
となり、余りは $2$ である。$2^{100}$ は 31 桁の数なので、直接 7 で割るのは大変である。
一の位は 10 で割った余りである。$7$ の累乗を計算すると
$$
7^1=7,\qquad 7^2=49,\qquad 7^3=343,\qquad 7^4=2401
$$
で、一の位は $7,9,3,1$ である。$7^4$ の一の位が $1$ なので、「$7^4$ を $1$ に置き換えてよい」とすると、$7^5,7^6,\dots$ の一の位は再び $7,9,3,1,\dots$ とくり返す。$2026=4\cdot506+2$ だから、「$10$ で割った余りが等しい」ことを $\pmod{10}$ をつけた $\equiv$ で表すと
$$
7^{2026}=\left(7^4\right)^{506}\cdot7^2\equiv1^{506}\cdot49\equiv9\pmod{10}
$$
であり、一の位は $9$ である。
3 つの計算はどれも、大きな数を「同じ余りをもつ小さな数」に置き換えている。この置き換えが正しいことを確かめたい。この記事で答える問いは次の 3 つである。
- 余りどうしで足し算・引き算・掛け算をしてよいのはなぜか。→ thm-cgrr-rules
- 累乗や、多項式に代入した値の余りも、余りだけで決まるのはなぜか。→ cor-cgrr-power、thm-cgrr-poly
- 逆に、置き換えてはいけないものはあるか。→ ex-cgrr-exponent、ex-cgrr-cancel
高校の計算と、この記事で使う言葉、大学での言葉の対応は次のとおりである。表の記号 $\overline a$（$a$ の剰余類）と $\mathbb{Z}/n\mathbb{Z}$ は、def-cgrr-class で定義する。高校の計算 この記事の言葉 大学の言葉 余りが同じ数を同じとみなす 合同 $a\equiv b\pmod n$ 同値関係 余りで整数をグループに分ける 剰余類 $\overline a$ 同値類 余りどうしで計算する 和・差・積の合同 剰余環 $\mathbb{Z}/n\mathbb{Z}$ の演算 余りで場合分けする 多項式の値の合同 $\mathbb{Z}/n\mathbb{Z}$ の元を全部調べる
合同の定義
以下、$n$ は正の整数とする。主に $n\ge2$ の場合を考える（$n=1$ ではどの 2 つの整数も合同になる）。
整数 $a,b$ について、差 $a-b$ が $n$ で割り切れるとき、$a$ と $b$ は $n$ を法として合同 であるといい、
$$
a\equiv b\pmod n
$$
と書く。この形の式を 合同式 といい、$n$ を 法 という。$a-b$ が $n$ で割り切れないときは $a\not\equiv b\pmod n$ と書く。
- $17\equiv2\pmod 5$ である。差が $17-2=15=5\cdot3$ で、$5$ で割り切れるからである。
- $-3\equiv4\pmod 7$ である。差が $-3-4=-7=7\cdot(-1)$ で、$7$ で割り切れるからである。
- $23\not\equiv5\pmod 4$ である。差 $23-5=18$ は $4\cdot4=16$ と $4\cdot5=20$ の間にあり、$4$ で割り切れないからである。
除法の原理 により、整数 $a$ は
$$
a=nq+r\qquad(q\text{ は整数},\ 0\le r< n)
$$
とただ 1 通りに書ける。この $r$ を、$a$ を $n$ で割った 余り という。$a$ が負の数でも、余りは $0$ 以上 $n$ 未満にとる。
- $-3$ を $7$ で割る。$-3=7\cdot(-1)+4$ で $0\le4<7$ なので、余りは $4$ である。$-3=7\cdot0+(-3)$ とも書けるが、$-3$ は $0\le r<7$ を満たさないので余りではない。
- $-17$ を $5$ で割る。$-17=5\cdot(-4)+3$ で $0\le3<5$ なので、余りは $3$ である。
ex-cgrr-def の $-3\equiv4\pmod7$ では、$-3$ と $4$ を $7$ で割った余りはどちらも $4$ である。一般に次が成り立つ。
整数 $a,b$ について、$a\equiv b\pmod n$ であることと、$a$ と $b$ を $n$ で割った余りが等しいことは同値である。
方針：$a$ と $b$ を商と余りで書き、差 $a-b$ を計算する。
段 1（書き表す）。$a=nq+r$、$b=nq'+r'$（$q,q'$ は整数、$0\le r< n$、$0\le r'< n$）と書く。引き算すると
$$
a-b=(nq+r)-(nq'+r')=n(q-q')+(r-r')
$$
である。
段 2（余りが等しければ合同）。$r=r'$ とする。段 1 の式で $r-r'=0$ なので $a-b=n(q-q')$ となり、$a-b$ は $n$ で割り切れる。よって $a\equiv b\pmod n$ である。
段 3（合同ならば余りが等しい）。$a\equiv b\pmod n$ とし、$a-b=nk$（$k$ は整数）と書く。段 1 の式を $r-r'$ について解くと
$$
r-r'=(a-b)-n(q-q')=nk-n(q-q')=n(k-q+q')
$$
なので、$r-r'$ は $n$ の倍数である。一方、$r< n$ と $r'\ge0$ から $r-r'< n-0=n$ であり、$r\ge0$ と $r'< n$ から $r-r'>0-n=-n$ である。まとめると
$$
-n< r-r'< n
$$
である。$-n$ より大きく $n$ より小さい $n$ の倍数は $0$ だけなので、$r-r'=0$、つまり $r=r'$ である。$\square$
この命題から、$n$ を法として合同な整数は「$n$ で割った余りが同じ整数」のことだと分かる。図 1 は、法 $7$ で余りが同じ整数を時計の同じ位置に並べたものである。
法 7 の余りの時計。同じ位置にある整数どうしは 7 を法として合同である
たとえば余り $2$ の位置には $-5,2,9,16$ が並び、このうちどの 2 つをとっても差は $7$ の倍数である。
合同式は、等号と同じように扱える次の性質をもつ。
すべての整数 $a,b,c$ について、次が成り立つ。
- $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$（推移律）
方針：どれも def-cgrr-congruence に戻り、差を $n$ の倍数の形に書く。
- $a-a=0=n\cdot0$ なので、$a-a$ は $n$ で割り切れる。
- $a-b=nk$（$k$ は整数）とする。$b-a=-(a-b)=-nk=n\cdot(-k)$ なので、$b-a$ も $n$ で割り切れる。
- $a-b=nk$、$b-c=nl$（$k,l$ は整数）とする。
$$ a-c=(a-b)+(b-c)=nk+nl=n(k+l) $$
なので、$a-c$ も $n$ で割り切れる。$\square$
- 反射律：$5\equiv5\pmod 3$ である。差は $5-5=0=3\cdot0$ で、$3$ で割り切れる。
- 対称律：$9-2=7$ なので $9\equiv2\pmod 7$ である。向きを逆にした差 $2-9=-7=7\cdot(-1)$ も $7$ で割り切れるので、$2\equiv9\pmod 7$ でもある。
- 推移律：$17-2=15=5\cdot3$ なので $17\equiv2\pmod 5$、$2-(-3)=5=5\cdot1$ なので $2\equiv-3\pmod 5$ である。推移律により $17\equiv-3\pmod 5$ となる。実際 $17-(-3)=20=5\cdot4$ である。差 $20$ は、2 つの差 $15$ と $5$ の和になっている（prf-cgrr-equiv の 3 の計算そのものである）。
この 3 つの性質をもつ関係を 同値関係 という。推移律があるので、合同式は $a\equiv b\equiv c\pmod n$ のように等号と同じ感覚でつないでよい。たとえば ex-cgrr-equiv の 3 つの数は $17\equiv2\equiv-3\pmod 5$ とつないで書ける。
主定理：和・差・積は余りだけで決まる
一般の証明の前に、小さな数で同じことを確かめる。
法 $7$ で考える。$17=7\cdot2+3$、$25=7\cdot3+4$ なので $17\equiv3$、$25\equiv4\pmod 7$ である。$17,25$ で計算した結果と、$3,4$ で計算した結果の余りを比べる。
| 計算 | $17$ と $25$ で | $3$ と $4$ で | 余り |
|---|---|---|---|
| 和 | $17+25=42=7\cdot6+0$ | $3+4=7=7\cdot1+0$ | どちらも $0$ |
| 差 | $17-25=-8=7\cdot(-2)+6$ | $3-4=-1=7\cdot(-1)+6$ | どちらも $6$ |
| 積 | $17\cdot25=425=7\cdot60+5$ | $3\cdot4=12=7\cdot1+5$ | どちらも $5$ |
積の余りが一致する理由は、$17=3+7\cdot2$、$25=4+7\cdot3$ を代入して展開すると見える。
$$
\begin{aligned}
17\cdot25&=(3+7\cdot2)(4+7\cdot3)\\
&=3\cdot4+3\cdot(7\cdot3)+(7\cdot2)\cdot4+(7\cdot2)(7\cdot3)\\
&=12+7\cdot(9+8+42)=12+7\cdot59 .
\end{aligned}
$$
$3\cdot4=12$ 以外の項はすべて $7$ の倍数なので、$17\cdot25$ と $12$ の差は $7$ の倍数になる。
この計算を文字で行うと、次の定理になる。
整数 $a,a',b,b'$ が
$$
a\equiv a'\pmod n,\qquad b\equiv b'\pmod n
$$
を満たすならば、
$$
a+b\equiv a'+b',\qquad a-b\equiv a'-b',\qquad ab\equiv a'b'\pmod n
$$
である。
方針：仮定を「$a'$ は $a$ に $n$ の倍数を足したもの」と書き直す。そのうえで、和・差・積のそれぞれについて 2 つの結果の差を「（もとの数で計算した結果）−（置き換えた数で計算した結果）」の向きで計算し、$n$ の倍数になることを確かめる。この向きは def-cgrr-congruence の「$a-b$ が $n$ で割り切れる」と同じ向きなので、定義からそのまま結論が出る。
段 1（仮定を書き直す）。$a\equiv a'$ なので、def-cgrr-congruence により $a-a'=nk$ となる整数 $k$ がある。$s:=-k$ とおくと $a'=a+ns$ である。同じように、$b'=b+nt$ となる整数 $t$ がある。
段 2（和）。段 1 の $a'=a+ns$、$b'=b+nt$ を代入すると
$$
(a+b)-(a'+b')=a+b-(a+ns)-(b+nt)=-ns-nt=n(-s-t)
$$
である。$-s-t$ は整数なので、$(a+b)-(a'+b')$ は $n$ で割り切れる。def-cgrr-congruence により $a+b\equiv a'+b'$ である。
段 3（差）。同じように代入すると
$$
(a-b)-(a'-b')=a-b-(a+ns)+(b+nt)=-ns+nt=n(t-s)
$$
である。$t-s$ は整数なので、$(a-b)-(a'-b')$ は $n$ で割り切れる。def-cgrr-congruence により $a-b\equiv a'-b'$ である。
段 4（積）。$a'b'$ を展開すると
$$
a'b'=(a+ns)(b+nt)=ab+a\cdot nt+ns\cdot b+ns\cdot nt
$$
である。したがって
$$
ab-a'b'=ab-(ab+ant+nbs+n^2st)=-ant-nbs-n^2st=n(-at-bs-nst)
$$
である。$-at-bs-nst$ は整数なので、$ab-a'b'$ は $n$ で割り切れる。def-cgrr-congruence により $ab\equiv a'b'$ である。$\square$
- $38\cdot45+29$ を $6$ で割った余りを求める。
$$ 38=6\cdot6+2,\qquad 45=6\cdot7+3,\qquad 29=6\cdot4+5 $$
なので $38\equiv2$、$45\equiv3$、$29\equiv5\pmod 6$ である。thm-cgrr-rules の積の規則で $38\cdot45\equiv2\cdot3=6$、和の規則で
$$ 38\cdot45+29\equiv6+5=11=6\cdot1+5\pmod 6 $$
であり、余りは $5$ である。実際に計算すると $38\cdot45+29=1710+29=1739=6\cdot289+5$ で、確かに余りは $5$ である。 - $123\cdot456$ を $9$ で割った余りを求める。$123=9\cdot13+6$、$456=9\cdot50+6$ なので
$$ 123\cdot456\equiv6\cdot6=36=9\cdot4\equiv0\pmod 9 $$
であり、$123\cdot456$ は $9$ で割り切れる。実際 $123\cdot456=56088=9\cdot6232$ である。
掛け算をくり返すと累乗になる。
$a\equiv a'\pmod n$ ならば、すべての正の整数 $k$ について $a^k\equiv a'^k\pmod n$ である。
方針：thm-cgrr-rules の積の規則を、$k$ を 1 ずつ増やしながらくり返し使う。
段 1（$k=1$ のとき）。$a^1=a$、$a'^1=a'$ なので、主張は仮定 $a\equiv a'$ そのものである。
段 2（$k$ のときから $k+1$ のときへ）。ある正の整数 $k$ について $a^k\equiv a'^k$ が成り立つとする。この式と仮定 $a\equiv a'$ の 2 つに積の規則を使うと
$$
a^k\cdot a\equiv a'^k\cdot a'\pmod n ,
$$
つまり $a^{k+1}\equiv a'^{k+1}\pmod n$ である。
段 1 と段 2 から、数学的帰納法 により、すべての正の整数 $k$ について主張が成り立つ。$\square$
- ex-cgrr-pow の計算を、規則を示しながらやり直す。$2^3=8\equiv1\pmod 7$ に cor-cgrr-power（$k=33$）を使うと
$$ \left(2^3\right)^{33}\equiv1^{33}=1\pmod 7 . $$
これと $2\equiv2$ に積の規則を使うと、$2^{100}=\left(2^3\right)^{33}\cdot2\equiv1\cdot2=2\pmod 7$ である。 - $3^{50}$ を $8$ で割った余りを求める。$3^2=9=8\cdot1+1$ なので $3^2\equiv1\pmod 8$ である。$50=2\cdot25$ だから、cor-cgrr-power により
$$ 3^{50}=\left(3^2\right)^{25}\equiv1^{25}=1\pmod 8 $$
であり、余りは $1$ である。
足し算・掛け算・累乗を組み合わせると、多項式になる。
$f(x)=x^2+x+1$ とする。$f(100)=10000+100+1=10101$ を $7$ で割った余りを、割り算せずに求める。$100\equiv2\pmod 7$ なので、$100$ を $2$ に置き換えて
$$
f(100)=100^2+100+1\equiv2^2+2+1=7\equiv0\pmod 7
$$
となる。よって $10101$ は $7$ の倍数である。実際 $10101=7\cdot1443$ である。
係数 $c_0,c_1,\dots,c_m$ がすべて整数である多項式
$$
f(x)=c_mx^m+c_{m-1}x^{m-1}+\cdots+c_1x+c_0
$$
を考える。整数 $a,b$ が $a\equiv b\pmod n$ を満たすならば、$f(a)\equiv f(b)\pmod n$ である。
方針：各項 $c_kx^k$ ごとに合同式を作り、それらを和の規則で足し合わせる。
段 1（1 つの項）。$1\le k\le m$ とする。cor-cgrr-power により $a^k\equiv b^k$ である。prop-cgrr-equiv の反射律により $c_k\equiv c_k$ である。この 2 つに thm-cgrr-rules の積の規則を使うと
$$
c_ka^k\equiv c_kb^k\pmod n
$$
である。定数項 $c_0$ については、反射律により $c_0\equiv c_0$ である。
段 2（足し合わせる）。段 1 の合同式を、和の規則で 1 つずつ足していく。まず $c_0\equiv c_0$ と $c_1a\equiv c_1b$ を足して
$$
c_0+c_1a\equiv c_0+c_1b\pmod n
$$
を得る。これに $c_2a^2\equiv c_2b^2$ を足して $c_0+c_1a+c_2a^2\equiv c_0+c_1b+c_2b^2$ を得る。これを $c_ma^m\equiv c_mb^m$ を足すところまで続ける（足した項の個数についての 数学的帰納法）と、最後に $f(a)\equiv f(b)\pmod n$ が得られる。$\square$
4 桁の整数 $N$ の千の位・百の位・十の位・一の位の数を $d_3,d_2,d_1,d_0$ とすると
$$
N=d_3\cdot10^3+d_2\cdot10^2+d_1\cdot10+d_0
$$
である。これは多項式 $f(x)=d_3x^3+d_2x^2+d_1x+d_0$ に $x=10$ を代入した値 $f(10)$ である。$10=9\cdot1+1$ なので $10\equiv1\pmod 9$ であり、thm-cgrr-poly により
$$
N=f(10)\equiv f(1)=d_3+d_2+d_1+d_0\pmod 9
$$
となる。つまり、$N$ を $9$ で割った余りは、各位の数の和を $9$ で割った余りに等しい。
たとえば $N=2026$ なら、各位の数の和は $2+0+2+6=10=9\cdot1+1$ なので、余りは $1$ である。実際 $2026=9\cdot225+1$ である。
余りで場合分けする
prop-cgrr-remainder により、どの整数 $a$ も $0,1,\dots,n-1$ のどれか 1 つとちょうど合同である。さらに thm-cgrr-poly により、$f(a)$ を $n$ で割った余りは、$a$ を $n$ で割った余りだけで決まる。したがって、「すべての整数 $a$ について $f(a)$ の余りは〜」という無限個の主張が、$a=0,1,\dots,n-1$ の $n$ 個を調べるだけで示せる。高校で「$n=2k,\ 2k+1$ で場合分けする」のは、この方法の $n=2$ の場合である。
$a$ を $4$ で割った余りを $r$ とすると、thm-cgrr-poly（$f(x)=x^2$）により $a^2\equiv r^2\pmod 4$ である。$r=0,1,2,3$ を全部調べる。
| $r$ | $0$ | $1$ | $2$ | $3$ |
|---|---|---|---|---|
| $r^2$ | $0$ | $1$ | $4$ | $9$ |
| $r^2$ を $4$ で割った余り | $0$ | $1$ | $0$ | $1$ |
よって、平方数を $4$ で割った余りは $0$ か $1$ である。ここから、2 つの平方数の和を $4$ で割った余りは $0+0=0$、$0+1=1$、$1+1=2$ のどれかであり、$3$ にはならない。たとえば $4$ で割って $3$ 余る $2027=4\cdot506+3$ は、2 つの平方数の和では書けない。
$f(x)=x^3-x$ とする。$n$ を $6$ で割った余りを $r$ とすると、thm-cgrr-poly により $f(n)\equiv f(r)\pmod 6$ である。$r=0,1,\dots,5$ を全部調べる。
| $r$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|---|---|---|---|---|---|---|
| $r^3-r$ | $0$ | $0$ | $6$ | $24$ | $60$ | $120$ |
| $6$ で割った余り | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |
どれも $6$ で割り切れるので、すべての整数 $n$ について $n^3-n$ は $6$ の倍数である。
剰余類：余りで整数をグループに分ける
prop-cgrr-remainder と図 1 は、整数全体が「$n$ で割った余り」によって $n$ 個のグループに分かれることを示している。このグループに名前をつける。
整数 $a$ に対し、$a$ と $n$ を法として合同な整数全体の集合
$$
\overline a:=\{\,b\in\mathbb{Z}\mid b\equiv a\pmod n\,\}=\{\dots,\ a-2n,\ a-n,\ a,\ a+n,\ a+2n,\ \dots\}
$$
を、$a$ の（$n$ を法とする）剰余類 という。剰余類全体の集合を $\mathbb{Z}/n\mathbb{Z}$ と書き、その和と積を
$$
\overline a+\overline b:=\overline{a+b},\qquad \overline a\cdot\overline b:=\overline{ab}
$$
で定める。この定め方で、剰余類の中からどの数を選んで計算しても同じ結果になること（代表の選び方によらないこと）は、rem-cgrr-welldef で確かめる。
この記事で「剰余類」というときは、いつもこの意味（$n$ を法として合同な整数全体の集合）である。
$n=3$ では
$$
\overline0=\{\dots,-3,0,3,6,\dots\},\quad \overline1=\{\dots,-2,1,4,7,\dots\},\quad \overline2=\{\dots,-1,2,5,8,\dots\}
$$
であり、整数全体がこの $3$ つに分かれる。$\overline4$ は $\overline1$ と同じ集合であり、$\overline{-1}$ は $\overline2$ と同じ集合である。$\mathbb{Z}/3\mathbb{Z}=\{\overline0,\overline1,\overline2\}$ で、たとえば $\overline2+\overline2=\overline4=\overline1$、$\overline2\cdot\overline2=\overline4=\overline1$ である。
ex-cgrr-mod3 では $\overline4=\overline1$ なので、$\overline4+\overline2$ を $\overline{4+2}=\overline6$ と計算しても、$\overline1+\overline2$ として $\overline{1+2}=\overline3$ と計算してもよいはずである。実際 $\overline6=\overline3=\overline0$ で一致する。一般には次の 2 段で確かめる。
段 1。$\overline a=\overline{a'}$ と $a\equiv a'$ は同値である。$\overline a=\overline{a'}$ なら、$a'\in\overline{a'}=\overline a$ なので $a'\equiv a$ である。逆に $a\equiv a'$ なら、$b\equiv a$ と $b\equiv a'$ は prop-cgrr-equiv の推移律と対称律により同値なので、$\overline a$ と $\overline{a'}$ は同じ集合である。
段 2。$\overline a=\overline{a'}$、$\overline b=\overline{b'}$ とすると、段 1 により $a\equiv a'$、$b\equiv b'$ であり、thm-cgrr-rules により $a+b\equiv a'+b'$、$ab\equiv a'b'$ である。段 1 をもう一度使うと $\overline{a+b}=\overline{a'+b'}$、$\overline{ab}=\overline{a'b'}$ である。つまり和と積は、剰余類の中からどの数を選んで計算しても同じ結果になる。
prop-cgrr-remainder により $\mathbb{Z}/n\mathbb{Z}=\{\overline0,\overline1,\dots,\overline{n-1}\}$ であり、これらは相異なる（$0\le r< r'< n$ なら余りが違うので合同でない）。和と積は整数の和と積をそのまま写したものなので、交換法則・結合法則・分配法則などの計算法則がそのまま成り立つ。このような集合を 可換環 といい、$\mathbb{Z}/n\mathbb{Z}$ を $n$ を法とする 剰余環 と呼ぶ。
$\mathbb{Z}/4\mathbb{Z}=\{\overline0,\overline1,\overline2,\overline3\}$ の和と積を表にする（$\overline a$ を $a$ と略して書く）。
| $+$ | $0$ | $1$ | $2$ | $3$ |
|---|---|---|---|---|
| $0$ | $0$ | $1$ | $2$ | $3$ |
| $1$ | $1$ | $2$ | $3$ | $0$ |
| $2$ | $2$ | $3$ | $0$ | $1$ |
| $3$ | $3$ | $0$ | $1$ | $2$ |
| $\times$ | $0$ | $1$ | $2$ | $3$ |
| --- | --- | --- | --- | --- |
| $0$ | $0$ | $0$ | $0$ | $0$ |
| $1$ | $0$ | $1$ | $2$ | $3$ |
| $2$ | $0$ | $2$ | $0$ | $2$ |
| $3$ | $0$ | $3$ | $2$ | $1$ |
たとえば $3\cdot3=9=4\cdot2+1$ なので $\overline3\cdot\overline3=\overline1$、$2\cdot2=4=4\cdot1+0$ なので $\overline2\cdot\overline2=\overline0$ である。
法 4 と法 5 の掛け算の表を並べたもの。赤い欄は、0 でない 2 数の積が 0 になる場所で、法 4 にだけある
図 2 は、ex-cgrr-table4 の法 $4$ の掛け算の表と、法 $5$ の掛け算の表を並べたものである。法 $4$ では $\overline2\cdot\overline2=\overline0$ の欄が赤くなる。法 $5$ の表では、$0$ の行と $0$ の列を除くと $0$ が 1 つもない（ex-cgrr-table5）。
図 2 の法 $5$ の表から 2 つの欄を計算で確かめる。$2\cdot3=6=5\cdot1+1$ なので $\overline2\cdot\overline3=\overline1$、$4\cdot4=16=5\cdot3+1$ なので $\overline4\cdot\overline4=\overline1$ である。同じように、$1$ から $4$ までの 2 数の積 $16$ 通りを $5$ で割ると、余りはどれも $1,2,3,4$ のどれかであり、$0$ にはならない。法 $4$ の $2\cdot2=4=4\cdot1+0$ とは違う。
整数では「$0$ でない 2 数の積は $0$ でない」が、$\mathbb{Z}/4\mathbb{Z}$ ではこれが成り立たず、$\mathbb{Z}/5\mathbb{Z}$ では成り立つ。この違いは、法が素数（$5$）か合成数（$4=2\cdot2$）かから来る。法が素数なら成り立つことは、合同式の割り算と逆元 で証明する。この違いが、次節の反例と割り算の話につながる。
二項係数を添字の余りでグループに分けて足す方法は 二項係数を余りで分けた和 で扱う。
例と反例
合同式では足し算・引き算・掛け算・累乗の底の置き換えができる。しかし、ふつうの等式でできることが何でもできるわけではない。
| 外した仮定・やりたい操作 | 崩れる主張 | ボックス |
|---|---|---|
| 指数を法 $n$ で置き換える | $k\equiv l\pmod n\Rightarrow a^k\equiv a^l$ | ex-cgrr-exponent |
| 両辺を同じ数で割る | $ac\equiv bc\Rightarrow a\equiv b$ | ex-cgrr-cancel |
| 積が $0$ なら因数のどちらかが $0$ | $ab\equiv0\Rightarrow a\equiv0$ または $b\equiv0$ | ex-cgrr-zerodiv |
$8=7\cdot1+1$ なので $8\equiv1\pmod 7$ である。しかし
$$
2^8=256=7\cdot36+4\equiv4,\qquad 2^1=2\pmod 7
$$
なので $2^8\not\equiv2^1\pmod 7$ である。cor-cgrr-power が許すのは累乗される数（底）の置き換えであり、指数の置き換えではない。ex-cgrr-pow で指数 $100$ を小さくできたのは、$2^3\equiv1$ を使ったからである。指数をどの数で割った余りに置き換えてよいかは、冪の余りの周期と元の位数 で扱う。
$2\cdot3=6$、$2\cdot8=16$ で、差 $16-6=10$ は $10$ で割り切れるので
$$
2\cdot3\equiv2\cdot8\pmod{10}
$$
である。しかし $8-3=5$ は $10$ で割り切れないので、$3\not\equiv8\pmod{10}$ である。両辺を $2$ で割ることはできない。thm-cgrr-rules は和・差・積についての定理であり、割り算については何も言っていない。割ってよい条件は 合同式の割り算と逆元 で証明する（答は、割る数と法の最大公約数が $1$ であること）。
$2\cdot3=6=6\cdot1$ なので $2\cdot3\equiv0\pmod 6$ である。しかし $2\not\equiv0$、$3\not\equiv0\pmod 6$ である。ex-cgrr-table4 と図 2 の $\overline2\cdot\overline2=\overline0$（法 $4$）も同じ現象である。整数では「$ab=0$ ならば $a=0$ または $b=0$」が成り立つが、法 $6$ や法 $4$ の合同式では成り立たない。法が素数のときには成り立つことが、合同式の割り算と逆元 で示される。
さらに先へ
- 割り算：合同式の両辺をいつ割ってよいか、1 次の合同式 $ax\equiv b\pmod n$ をどう解くかは 合同式の割り算と逆元 で扱う。
- 累乗の余り：素数 $p$ を法とすると $a^{p-1}\equiv1$（$p\nmid a$ のとき）が成り立つ。これは Fermatの小定理と冪の余り で、累乗の余りの周期は 冪の余りの周期と元の位数 で扱う。
- 大学では、$\mathbb{Z}/n\mathbb{Z}$ を「整数全体の環 $\mathbb{Z}$ を、$n$ の倍数全体 $n\mathbb{Z}$（イデアル）で割った環」と見る。多項式を多項式で割った余りでも、同じ作り方で環ができる。
- 歴史：合同の記号 $\equiv$ は、Gauss が『Disquisitiones Arithmeticae』（1801 年）の第 2 条で導入した（Gau01）。
関連項目
- 前提: 整数, 除法の原理, 数学的帰納法
- 全体の案内: 合同式と余りの世界
- 前に読む: 整数の割り算と互除法
- 次に読む: 合同式の割り算と逆元, Fermatの小定理と冪の余り, 冪の余りの周期と元の位数, 倍数の判定法
- 関連（高校数学）: 二項係数を余りで分けた和, 整数の筆算の仕組み, 剰余の定理と因数定理, 循環小数と分数
- 同じ主題の用語解説: 合同式, 剰余類, 剰余環
- 発展: 同値関係, 可換環, イデアル
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
