合同式と余りの世界

同義語：congruences and residues

概要

前提知識: 整数, 除法の原理
「100 日後は何曜日か」「$2^{100}$ を $7$ で割った余りはいくつか」「一の位はどうくり返すか」。高校で出会うこうした問題は、どれも 割った余りだけで計算する ことで解ける。この記事は、余りの計算（合同式）を扱う 4 本の記事への案内である。合同式の定義を短く述べたあと、高校の計算と大学の概念の対応を表にし、どの順番で何を読めばよいかを示す。

合同式とは

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

n を法とする合同

整数 $a,b$ について、差 $a-b$ が $n$ で割り切れるとき、$a$ と $b$ は $n$ を法として合同 であるといい、
$$ a\equiv b\pmod n $$
と書く。この形の式を 合同式 といい、$n$ を法という。

$a\equiv b\pmod n$ であることは、「$a$ と $b$ を $n$ で割った余りが等しい」ことと同じである。この言いかえの証明は合同式の計算規則にある。

合同式の例

$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$ に置き換えてよい理由が、合同式の計算規則の主題である。

図 1 は、法 $7$ で余りが同じ整数を時計の同じ位置に並べたものである。同じ位置にある整数どうしは $7$ を法として合同である。
図1：法 7 の余りの時計。同じ位置にある整数どうしは 7 を法として合同である

高校の計算と大学の概念

高校で使う余りの計算の技法は、大学では次の概念の特別な場合として整理される。右の列は、その内容を扱う記事である。

高校の計算	大学の概念	記事
余りが同じ数を同じとみなす	同値関係・剰余類	合同式の計算規則
余りどうしで足し算・掛け算をする	剰余環 $\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 本は、前の記事の結果を後の記事で使うように並んでいる。はじめて学ぶときは ① から順に読むとよい。各記事は、使う前の記事の結果を短く言い直してあるので、必要な記事だけを読むこともできる。

合同式の計算規則：余りどうしで足し算・引き算・掛け算・累乗をしてよい理由を証明する。整数係数の多項式に代入した値の余りが余りだけで決まることから、「余りで場合分けすれば有限個の確認で済む」ことや、9 で割った余りと各位の数の和の関係が分かる。
合同式の割り算と逆元：合同式の両辺を割ってよいのは、割る数と法の最大公約数が $1$ のときであることを、Bézout の等式を使って証明する。逆元を互除法で求める方法と、1 次合同式 $ax\equiv b\pmod n$ の解がいつ、いくつあるかが分かる。
Fermatの小定理と冪の余り：素数 $p$ と $p$ で割り切れない $a$ について $a^{p-1}\equiv1\pmod p$ となることを、余りの並べ替えを使って証明する。大きな指数を $p-1$ で割った余りに置き換える方法と、逆元を $a^{p-2}$ で求める方法が分かる。
冪の余りの周期と元の位数：$\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 問は位数を最小の素因数で押さえる問題なので ④ に置いた。どちらも「高校数学で解く」と「大学数学で見ると」を並べている。

合同式でしてよいこと・いけないこと

合同式は等式とよく似ているが、等式でできることが何でもできるわけではない。4 本の記事の内容を、使うときの注意としてまとめておく。

してよい計算といけない計算

してよい：$17\equiv3$、$25\equiv4\pmod 7$ なら、$17\cdot25=425=7\cdot60+5$ と $3\cdot4=12=7\cdot1+5$ の余りは等しい。和・差・積・累乗の底は、同じ余りの数に置き換えてよい（①）。
いけない：$8\equiv1\pmod 7$ だが、$2^8=256=7\cdot36+4$ なので $2^8\not\equiv2^1\pmod 7$ である。指数は法 $7$ では置き換えられない。置き換えてよいのは、位数（$2$ なら $3$）や $p-1=6$ を法として合同なときである（③・④）。
いけない：$2\cdot3\equiv2\cdot8\pmod{10}$ だが、$3\not\equiv8\pmod{10}$ である。割る数 $2$ と法 $10$ が公約数 $2$ をもつので、両辺を $2$ で割れない（②）。

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

さらに先へ

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