合同式と余りの世界

同義語:congruences and residues

概要

合同式と余りの世界(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)$ を割る。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 整数, 除法の原理

「100 日後は何曜日か」「$2^{100}$ を $7$ で割った余りはいくつか」「一の位はどうくり返すか」。高校で出会うこうした問題は、どれも 割った余りだけで計算する ことで解ける。この記事は、余りの計算(合同式)を扱う 4 本の記事への案内である。合同式を定義し、「合同とは余りが等しいこと」と「余りどうしで足し算・掛け算をしてよいこと」の 2 つをこの記事の中で証明する。そのあと、高校の計算と大学の概念の対応を表にし、どの順番で何を読めばよいかを示し、最後に合同式で「してはいけない計算」を反例で確かめる。

合同式とは

以下、$n$ は正の整数とする。

$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)。

合同式の例
  • $17\equiv2\pmod 5$ である。差が $17-2=15=5\cdot3$ だからである。$17$ も $2$ も、$5$ で割った余りは $2$ である。
  • $-3\equiv4\pmod 7$ である。差が $-3-4=-7=7\cdot(-1)$ だからである。$-3=7\cdot(-1)+4$ なので、$-3$ を $7$ で割った余りも $4$ である。
  • $23\not\equiv5\pmod 4$ である。差 $23-5=18$ は $4$ で割り切れない。
余りだけで計算する

今日が月曜日なら、$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 を法として合同である 法 7 の余りの時計。同じ位置にある整数どうしは 7 を法として合同である

合同式の 2 つの基本事実

この節では、合同式を使うときにいつも頼りにする 2 つの事実を証明する。どちらも ① 合同式の計算規則 の出発点で、そちらではさらに多項式への代入や倍数の判定まで進む。

この節で使う事実

除法の原理:整数 $a$ と正の整数 $n$ について、
$$ a=nq+r,\qquad0\le r< n $$
を満たす整数 $q,r$ がただ 1 組ある(除法の原理。この記事では証明しない)。この $r$ を、$a$ を $n$ で割った余りという。$a$ が負でも、余りは $0$ 以上 $n$ 未満にとる。

余りを求める
  • $23=4\cdot5+3$、$5=4\cdot1+1$ なので、$4$ で割った余りは $3$ と $1$ で、等しくない。ex-cgr-examples で $23\not\equiv5\pmod 4$ だったことと合っている。
  • $-3=7\cdot(-1)+4$ なので、$-3$ を $7$ で割った余りは $4$ である。$-3=7\cdot0+(-3)$ とも書けるが、$-3$ は $0$ 以上でないので余りではない。
合同と余り

整数 $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$ の倍数」と書き直し、示したい式の差も $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 で確かめる。

規則を使って余りを求める
  1. $17\cdot25$ を $7$ で割った余り:$17\equiv3$、$25\equiv4\pmod 7$ なので、(iii) により $17\cdot25\equiv3\cdot4=12\equiv5\pmod 7$ である。実際 $17\cdot25=425=7\cdot60+5$ である。
  2. $2^{100}$ を $7$ で割った余り:ex-cgr-weekday の計算は、$2^3\equiv1\pmod 7$ に (iv) を使って $(2^3)^{33}\equiv1^{33}$ とし、(iii) で $2$ を掛けたものである。
  3. 各位の数の和:$10\equiv1\pmod 9$ なので、(iv) により $10^k\equiv1\pmod 9$ である。$4725=4\cdot10^3+7\cdot10^2+2\cdot10+5$ に (i)(iii) を使うと $4725\equiv4+7+2+5=18\equiv0\pmod 9$ で、$4725$ は $9$ で割り切れる。実際 $4725=9\cdot525$ である。
余りで場合分けする:平方数を 4 で割った余り

どの整数 $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 つの記事と読み進め方

この記事で使った除法の原理と、② で使う互除法は、整数の割り算と互除法 で扱う。4 本は、前の記事の結果を後の記事で使うように並んでいる。はじめて学ぶときは ① から順に読むとよい。各記事は、使う前の記事の結果を短く言い直してあるので、必要な記事だけを読むこともできる。

  1. 合同式の計算規則:余りどうしで足し算・引き算・掛け算・累乗をしてよい理由を証明する。整数係数の多項式に代入した値の余りが余りだけで決まることから、「余りで場合分けすれば有限個の確認で済む」ことや、9 で割った余りと各位の数の和の関係が分かる。
  2. 合同式の割り算と逆元:合同式の両辺を割ってよいのは、割る数と法の最大公約数が $1$ のときであることを、Bézout の等式を使って証明する。逆元を互除法で求める方法と、1 次合同式 $ax\equiv b\pmod n$ の解がいつ、いくつあるかが分かる。
  3. Fermatの小定理と冪の余り:素数 $p$ と $p$ で割り切れない $a$ について $a^{p-1}\equiv1\pmod p$ となることを、余りの並べ替えを使って証明する。大きな指数を $p-1$ で割った余りに置き換える方法と、逆元を $a^{p-2}$ で求める方法が分かる。
  4. 冪の余りの周期と元の位数:$\gcd(a,n)=1$ のとき累乗の余りがくり返す周期(位数)を定義し、位数が $\varphi(n)$($1$ 以上 $n$ 以下で $n$ と互いに素な整数の個数)を割ることを、余りを同じ大きさの組に分けて証明する。Euler の定理と、Fermat の小定理のもう 1 つの証明が得られる。
どの疑問にどの記事が答えるか
疑問答える記事
余りどうしで計算してよいのはなぜか① 合同式の計算規則
指数も法 $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$ なら割ってよいことが ② 合同式の割り算と逆元 で証明される。

反例:合成数を法とすると、0 でない数の積が 0 になる

$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 の小定理の形は合成数では成り立たず、逆も成り立たない

③ で扱う Fermat の小定理は、素数 $p$ と $p\nmid a$ について $a^{p-1}\equiv1\pmod p$ と主張する。

  1. 法が素数でないと成り立たない:$n=4$、$a=3$ とすると $\gcd(3,4)=1$ だが、$3^3=27=4\cdot6+3$ なので $3^{4-1}\equiv3\not\equiv1\pmod 4$ である。
  2. 逆は成り立たない:$2^{10}=1024=3\cdot341+1$ なので $2^{10}\equiv1\pmod{341}$ であり、(iv) により $2^{340}=\bigl(2^{10}\bigr)^{34}\equiv1^{34}=1\pmod{341}$ である。しかし $341=11\cdot31$ は素数でない。「$a^{n-1}\equiv1\pmod n$」を満たしても、「$n$ は素数」は成り立たない。
    合成数を法としたときに正しく成り立つ形(Euler の定理)は ④ 冪の余りの周期と元の位数 で証明される。

どの反例も、「法と互いに素かどうか」「法が素数かどうか」で結果が変わることを示している。この 2 つの条件が、4 本の記事を通じてくり返し現れる。

発展

  • 法が互いに素な 2 つの合同式を同時に解く方法は 中国剰余定理 で扱う。
  • 素数 $p$ を法とすると、累乗の余りが $1,2,\dots,p-1$ をすべて尽くす数がある(原始根)。
  • $\mathbb{Z}/p\mathbb{Z}$ のほかにも、元の個数が $p^k$ の体がある(有限体)。符号理論や暗号で使われる。
  • 合同の記号 $\equiv$ は、Gauss が『Disquisitiones Arithmeticae』(1801 年)の第 2 条で導入した(Gau01)。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する