合同式と余りの世界(congruences and residues)とは、整数を正の整数 $n$ で割った余りで計算する合同式 $a\equiv b\pmod n$(差 $a-b$ が $n$ で割り切れること)を扱う 4 本の記事への案内である。合同は $a$ と $b$ を $n$ で割った余りが等しいことと同値であり、和・差・積と累乗の底は、同じ余りの数に置き換えてよい。一方、指数を法 $n$ で置き換えることや、法と公約数をもつ数で両辺を割ることはできない。法 $n$ で $a$ の逆元があるのは $\gcd(a,n)=1$ のときに限り、素数 $p$ と $p\nmid a$ については $a^{p-1}\equiv1\pmod p$(Fermat の小定理)が成り立ち、$\gcd(a,n)=1$ なら累乗の余りの周期は $\varphi(n)$ を割る。
「100 日後は何曜日か」「$2^{100}$ を $7$ で割った余りはいくつか」「一の位はどうくり返すか」。高校で出会うこうした問題は、どれも 割った余りだけで計算する ことで解ける。この記事は、余りの計算(合同式)を扱う 4 本の記事への案内である。合同式を定義し、「合同とは余りが等しいこと」と「余りどうしで足し算・掛け算をしてよいこと」の 2 つをこの記事の中で証明する。そのあと、高校の計算と大学の概念の対応を表にし、どの順番で何を読めばよいかを示し、最後に合同式で「してはいけない計算」を反例で確かめる。
以下、$n$ は正の整数とする。
整数 $a,b$ について、差 $a-b$ が $n$ で割り切れるとき、$a$ と $b$ は $n$ を法として合同 であるといい、
$$
a\equiv b\pmod n
$$
と書く。この形の式を 合同式 といい、$n$ を 法 という。
$a\equiv b\pmod n$ であることは、「$a$ と $b$ を $n$ で割った余りが等しい」ことと同じである。この言いかえは次の節で証明する(prop-cgr-remainder)。
今日が月曜日なら、$100=7\cdot14+2$ なので、100 日後は 98 日後(月曜日)の 2 日後で水曜日である。日数は $100\equiv2\pmod 7$ と置き換えてよい。
$2^{100}$ を $7$ で割った余りは、$2^3=8\equiv1\pmod 7$ と $100=3\cdot33+1$ を使うと
$$
2^{100}=\left(2^3\right)^{33}\cdot2\equiv1^{33}\cdot2=2\pmod 7
$$
と求まる。$2^3$ を余りの $1$ に置き換えてよい理由は、次の節の thm-cgr-rules で証明する。
図 1 は、法 $7$ で余りが同じ整数を時計の同じ位置に並べたものである。同じ位置にある整数どうしは $7$ を法として合同である。
法 7 の余りの時計。同じ位置にある整数どうしは 7 を法として合同である
この節では、合同式を使うときにいつも頼りにする 2 つの事実を証明する。どちらも ① 合同式の計算規則 の出発点で、そちらではさらに多項式への代入や倍数の判定まで進む。
除法の原理:整数 $a$ と正の整数 $n$ について、
$$
a=nq+r,\qquad0\le r< n
$$
を満たす整数 $q,r$ がただ 1 組ある(除法の原理。この記事では証明しない)。この $r$ を、$a$ を $n$ で割った余りという。$a$ が負でも、余りは $0$ 以上 $n$ 未満にとる。
整数 $a,b$ と正の整数 $n$ について、$a\equiv b\pmod n$ であることと、$a$ と $b$ を $n$ で割った余りが等しいことは同値である。
方針:$a-b$ を「$n$ の倍数」と「余りの差」に分け、余りの差が $-n$ より大きく $n$ より小さいことを使う。
段 1(書き表す)。除法の原理(rem-cgr-premises)により
$$
a=nq_1+r_1,\qquad b=nq_2+r_2,\qquad0\le r_1< n,\quad0\le r_2< n
$$
と書ける。引き算すると
$$
a-b=n(q_1-q_2)+(r_1-r_2)
$$
である。
段 2(余りが等しいなら合同)。$r_1=r_2$ なら、段 1 の式は $a-b=n(q_1-q_2)$ となり、$a-b$ は $n$ で割り切れる。よって $a\equiv b\pmod n$ である。
段 3(合同なら余りが等しい)。$a-b$ が $n$ で割り切れるとし、$a-b=nm$($m$ は整数)と書く。段 1 の式から
$$
r_1-r_2=(a-b)-n(q_1-q_2)=n\bigl(m-q_1+q_2\bigr)
$$
なので、$r_1-r_2$ は $n$ の倍数 $nk$($k=m-q_1+q_2$ は整数)である。一方、$0\le r_1< n$ と $-n< -r_2\le0$ を足すと $-n< r_1-r_2< n$ である。$-n< nk< n$ を $n>0$ で割って $-1< k<1$ で、この範囲の整数は $k=0$ だけである。よって $r_1=r_2$ である。$\square$
「余りが等しい」という関係は、自分自身と成り立ち、向きを入れかえても成り立ち、2 つつなげても成り立つ。prop-cgr-remainder により、合同 $\equiv$ も同じ 3 つの性質をもつ。大学ではこのような関係を 同値関係 という。
$a\equiv a'\pmod n$ かつ $b\equiv b'\pmod n$ ならば、次が成り立つ。
(R1) $a+b\equiv a'+b'\pmod n$
(R1) $a-b\equiv a'-b'\pmod n$
(R1) $ab\equiv a'b'\pmod n$
(R1) すべての正の整数 $k$ について $a^k\equiv a'^k\pmod n$
方針:仮定を「差が $n$ の倍数」と書き直し、示したい式の差も $n$ の倍数になることを、式変形で確かめる。
段 1(仮定を書き直す)。仮定から、整数 $s,t$ で $a-a'=ns$、$b-b'=nt$ と書ける。
段 2(和と差)。
$$
(a+b)-(a'+b')=(a-a')+(b-b')=n(s+t),\qquad(a-b)-(a'-b')=(a-a')-(b-b')=n(s-t)
$$
で、どちらも $n$ の倍数である。よって (i)(ii) が成り立つ。
段 3(積)。$a'b$ を引いて足すと
$$
ab-a'b'=(ab-a'b)+(a'b-a'b')=(a-a')b+a'(b-b')=n(sb+a't)
$$
で、$sb+a't$ は整数なので $n$ の倍数である。よって (iii) が成り立つ。
段 4(累乗)。$k$ についての帰納法で示す。$k=1$ では仮定そのものである。ある $k$ で $a^k\equiv a'^k\pmod n$ が成り立つとする。これと $a\equiv a'\pmod n$ に (iii) を使うと $a^k\cdot a\equiv a'^k\cdot a'\pmod n$、すなわち $a^{k+1}\equiv a'^{k+1}\pmod n$ である。よって (iv) が成り立つ。$\square$
thm-cgr-rules の (iv) で置き換えてよいのは底の $a$ であり、指数 $k$ ではない。指数を置き換えると誤ることは、ex-cgr-exponent で確かめる。
どの整数 $m$ も、prop-cgr-remainder により $4$ で割った余り $0,1,2,3$ のどれかと $4$ を法として合同である。(iv) により、$m^2$ は余りの 2 乗と合同なので、
| $m$ の余り | $0$ | $1$ | $2$ | $3$ |
|---|---|---|---|---|
| $m^2$ の余り | $0$ | $1$ | $4\equiv0$ | $9\equiv1$ |
となり、平方数を $4$ で割った余りは $0$ か $1$ である。無限にある整数を、4 つの場合の確認で調べ尽くした。したがって、2 つの平方数の和を $4$ で割った余りは $0+0$、$0+1$、$1+1$ の $0,1,2$ のどれかで、$3$ にはならない。たとえば $2027=4\cdot506+3$ は、2 つの平方数の和で書けない。
高校で使う余りの計算の技法は、大学では次の概念の特別な場合として整理される。右の列は、その内容を扱う記事である。
| 高校の計算 | 大学の概念 | 記事 |
|---|---|---|
| 余りが同じ数を同じとみなす | 同値関係・剰余類 | 合同式の計算規則 |
| 余りどうしで足し算・掛け算をする | 剰余環 $\mathbb{Z}/n\mathbb{Z}$ の演算 | 合同式の計算規則 |
| 余りで場合分けする | $\mathbb{Z}/n\mathbb{Z}$ の元を全部調べる | 合同式の計算規則 |
| 掛けて $1$ になる数を掛ける | 逆元(単元) | 合同式の割り算と逆元 |
| 互除法を逆にたどって $ax+ny=1$ を解く | Bézout の等式 | 合同式の割り算と逆元 |
| 素数の法なら $0$ 以外で割れる | 体 $\mathbb{F}_p$ | 合同式の割り算と逆元 |
| $a,2a,\dots,(p-1)a$ の余りは並べ替え | 単元の置換 | Fermatの小定理と冪の余り |
| $a^{p-1}$ を $1$ に置き換える | Fermat の小定理 | Fermatの小定理と冪の余り |
| 累乗の余りの周期 | 元の位数 | 冪の余りの周期と元の位数 |
| 周期は $p-1$ の約数 | 群の Lagrangeの定理 | 冪の余りの周期と元の位数 |
この記事で使った除法の原理と、② で使う互除法は、整数の割り算と互除法 で扱う。4 本は、前の記事の結果を後の記事で使うように並んでいる。はじめて学ぶときは ① から順に読むとよい。各記事は、使う前の記事の結果を短く言い直してあるので、必要な記事だけを読むこともできる。
| 疑問 | 答える記事 |
|---|---|
| 余りどうしで計算してよいのはなぜか | ① 合同式の計算規則 |
| 指数も法 $n$ で置き換えてよいか(答:いけない) | ①、③(素数 $p$ なら法 $p-1$ で置き換えてよい)、④(位数を法として置き換えてよい) |
| 合同式で割り算をしてよいのはいつか | ② 合同式の割り算と逆元 |
| $3x\equiv5\pmod 7$ のような式をどう解くか | ② |
| $a^{p-1}$ が $p$ を法として $1$ になるのはなぜか | ③ Fermatの小定理と冪の余り |
| 累乗の余りの周期は何を割るか | ④ 冪の余りの周期と元の位数 |
| 合成数を法とすると何が変わるか | ②(割り算)、③($a^{n-1}\equiv1$ が成り立たないことがある)、④(周期) |
数学オリンピックの問題も 2 問扱っている。国際数学オリンピック(2005 年)第 4 問は「$p-2$ 乗は逆元」という見方で解けるので ③ に、国際数学オリンピック(1999 年)第 4 問は位数を最小の素因数で押さえる問題なので ④ に置いた。どちらも「高校数学で解く」と「大学数学で見ると」を並べている。
合同式は等式とよく似ているが、等式でできることが何でもできるわけではない。してよいのは thm-cgr-rules の和・差・積と、累乗の底の置き換えである。それ以外の操作は、条件を満たさないと成り立たない。4 本の記事の内容を、使うときの注意として反例でまとめる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 置き換えるのは累乗の底だけ | $8\equiv1\pmod 7$ だが $2^8\not\equiv2^1\pmod 7$ | 指数を法 $n$ で置き換える(ex-cgr-exponent) |
| 割る数と法が互いに素 | $2\cdot3\equiv2\cdot8\pmod{10}$ | 両辺を同じ数で割る(ex-cgr-cancel) |
| 法が素数 | $2\cdot5\equiv0\pmod{10}$ | 積が $0$ と合同なら、どちらかが $0$ と合同(ex-cgr-zero-divisor) |
| 法が素数 | $3^3\equiv3\pmod 4$ | $\gcd(a,n)=1$ なら $a^{n-1}\equiv1\pmod n$(ex-cgr-fermat) |
| 結論から仮定へは戻れない | $2^{340}\equiv1\pmod{341}$、$341=11\cdot31$ | $a^{n-1}\equiv1\pmod n$ なら $n$ は素数(ex-cgr-fermat) |
$8\equiv1\pmod 7$ だが、$2^8=256=7\cdot36+4$ なので $2^8\equiv4$、一方 $2^1=2$ で、$2^8\not\equiv2^1\pmod 7$ である。満たす性質は「指数どうしが法 $7$ で合同」、成り立たないのは「累乗どうしが法 $7$ で合同」である。thm-cgr-rules の (iv) は底を置き換える規則で、証明の段 4 は同じ指数 $k$ のまま帰納法を進めている。指数を置き換えてよいのは、位数($2$ なら $3$)や $p-1=6$ を法として合同なときである(③・④)。実際 $8\equiv2\pmod 3$ で、$2^8\equiv2^2=4\pmod 7$ となり正しい余りが出る。
$2\cdot3=6$、$2\cdot8=16$ で差は $10$ なので $2\cdot3\equiv2\cdot8\pmod{10}$ である。しかし $3-8=-5$ は $10$ で割り切れず、$3\not\equiv8\pmod{10}$ である。満たす性質は「$ca\equiv cb$」、成り立たないのは「$a\equiv b$」である。割る数 $2$ と法 $10$ が公約数 $2$ をもつことが原因で、$\gcd(c,n)=1$ なら割ってよいことが ② 合同式の割り算と逆元 で証明される。
$2\not\equiv0$、$5\not\equiv0\pmod{10}$ だが、$2\cdot5=10\equiv0\pmod{10}$ である。整数では「$ab=0$ なら $a=0$ または $b=0$」だが、合成数 $10$ を法とする合同式ではこれが成り立たない。法が素数 $p$ なら成り立つ。$a\not\equiv0\pmod p$ なら $a$ は $p$ と互いに素で、② で証明されるとおり $a$ で両辺を割れるので、$ab\equiv a\cdot0\pmod p$ から $b\equiv0\pmod p$ が出るからである。この違いが、素数を法とする世界 $\mathbb{F}_p$ が体になる理由である(②)。
③ で扱う Fermat の小定理は、素数 $p$ と $p\nmid a$ について $a^{p-1}\equiv1\pmod p$ と主張する。
どの反例も、「法と互いに素かどうか」「法が素数かどうか」で結果が変わることを示している。この 2 つの条件が、4 本の記事を通じてくり返し現れる。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する