「余りで分類する」という考え方を、式の形で表したのが合同式です。
合同式を使いこなせば、余りに関する複雑な議論が、まるで普通の等式のようにスッキリ扱えます。
9-1で学んだ「余りによる整数の分類」を思い出しましょう。 たとえば、整数を $3$ で割った余りで分類すると、すべての整数は「余り $0$」「余り $1$」「余り $2$」の3つのグループに分かれます。 $23$ と $5$ は同じグループ（余り $2$）、$17$ と $8$ は同じグループ（余り $2$）です。
この「余りが等しい」という関係を、数学的に簡潔に表す記法が合同式です。
$a, b$ を整数、$m$ を正の整数とする。$a - b$ が $m$ の倍数であるとき、
$$a \equiv b \pmod{m}$$
と書き、「$a$ と $b$ は $m$ を法として合同である」と読む。
具体例を見てみましょう。
合同式 $\equiv$ は、普通の等号 $=$ と似た性質を持っています。 数学的に言えば、$\equiv \pmod{m}$ は同値関係です。 同値関係とは、次の3つの性質を満たす関係のことです。
1. 反射律：$a \equiv a \pmod{m}$（自分自身と合同）
2. 対称律：$a \equiv b \pmod{m}$ ならば $b \equiv a \pmod{m}$
3. 推移律：$a \equiv b \pmod{m}$ かつ $b \equiv c \pmod{m}$ ならば $a \equiv c \pmod{m}$
これらの性質のおかげで、$\equiv$ を $=$ と同じ感覚で使えるのです。 合同式の世界では、余りが等しい数を「同じもの」とみなすのです。
反射律：$a - a = 0 = m \times 0$ は $m$ の倍数。よって $a \equiv a \pmod{m}$。
対称律：$a \equiv b \pmod{m}$ のとき、$a - b = mk$（$k$ は整数）。 よって $b - a = m(-k)$ も $m$ の倍数。ゆえに $b \equiv a \pmod{m}$。
推移律：$a - b = mk$, $b - c = ml$ とすると、 $a - c = (a - b) + (b - c) = m(k + l)$ は $m$ の倍数。よって $a \equiv c \pmod{m}$。
✕ 誤：$23 = 5 \pmod{3}$ と書く
○ 正：$23 \equiv 5 \pmod{3}$ と書く
$23 = 5$ は明らかに偽ですが、$23 \equiv 5 \pmod{3}$ は真です。 合同式は「余りの世界での等しさ」を表す別の記号であり、通常の等号とは区別して書きます。 解答で $=$ と $\equiv$ を混同すると減点されることがあります。
次の3つの条件は、すべて同じことを意味します。 問題に応じて使い分けると便利です。
① $a - b$ が $m$ の倍数 （定義）
② $a = mq + b$（ある整数 $q$ が存在）
③ $a$ を $m$ で割った余りと $b$ を $m$ で割った余りが等しい
$m$ で割った余りが同じ整数をまとめたグループを剰余類（residue class）と呼びます。 たとえば $m = 3$ なら、すべての整数は $\{0, 3, 6, \ldots\}$、$\{1, 4, 7, \ldots\}$、$\{2, 5, 8, \ldots\}$ の3つの剰余類に分かれます。
大学の代数学では、この剰余類の集合 $\mathbb{Z}/m\mathbb{Z}$（$m$ を法とする剰余環）が重要な研究対象になります。 合同式の計算は、この剰余環での計算にほかなりません。 高校の合同式は、抽象代数学の入口に立っているのです。
合同式の最大の強みは、加法・減法・乗法が普通の等式と同じように使えることです。 両辺に同じ数を足す、引く、掛ける、さらにべき乗も取れます。
$a \equiv b \pmod{m}$, $c \equiv d \pmod{m}$ のとき：
1. 加法：$a + c \equiv b + d \pmod{m}$
2. 減法：$a - c \equiv b - d \pmod{m}$
3. 乗法：$ac \equiv bd \pmod{m}$
4. べき乗：$a^n \equiv b^n \pmod{m}$（$n$ は自然数）
$a \equiv b \pmod{m}$, $c \equiv d \pmod{m}$ とすると、$a - b = mk$, $c - d = ml$（$k, l$ は整数）。
加法：$(a + c) - (b + d) = (a - b) + (c - d) = m(k + l)$。$k + l$ は整数なので $a + c \equiv b + d \pmod{m}$。
乗法：$a = b + mk$ より $ac = (b + mk)c = bc + mkc$。同様に $c = d + ml$ より $ac = bc + mkc = b(d + ml) + mkc = bd + bml + mkc = bd + m(bl + kc)$。$bl + kc$ は整数なので $ac \equiv bd \pmod{m}$。
合同式の演算法則が意味するのは、余りの計算は、余りだけを使ってできるということです。
たとえば $23 \times 17$ を $5$ で割った余りを知りたいとき、わざわざ $23 \times 17 = 391$ を計算してから $5$ で割る必要はありません。 $23 \equiv 3 \pmod{5}$, $17 \equiv 2 \pmod{5}$ なので $23 \times 17 \equiv 3 \times 2 = 6 \equiv 1 \pmod{5}$。余りは $1$ です。
このように、大きな数を小さな余りに「縮めて」から計算できるのが合同式の威力です。
加法・減法・乗法は自由にできますが、割り算は常にできるわけではありません。 これは合同式で最も注意すべきポイントです。
✕ 誤：$6 \equiv 0 \pmod{6}$ の両辺を $2$ で割って $3 \equiv 0 \pmod{6}$
しかし $3 - 0 = 3$ は $6$ の倍数ではないので、$3 \equiv 0 \pmod{6}$ は偽です。
○ 正：$ac \equiv bc \pmod{m}$ のとき $a \equiv b \pmod{m}$ が成り立つのは、$c$ と $m$ が互いに素な場合に限ります。
上の例では $c = 2$ と $m = 6$ は $\gcd(2, 6) = 2 \neq 1$ なので互いに素でなく、割ることができません。
$ac \equiv bc \pmod{m}$ のとき：
$\gcd(c, m) = 1$（$c$ と $m$ が互いに素）ならば $a \equiv b \pmod{m}$
✕ 誤：$a \equiv b \pmod{5}$ と $c \equiv d \pmod{3}$ から $a + c \equiv b + d \pmod{???}$
○ 正：合同式の演算法則は、法（mod の数）が同じ場合にのみ使えます。 $\pmod{5}$ と $\pmod{3}$ の合同式を足すことはできません。 必ず法を揃えてから演算してください。
大学の代数学では、合同式での「割り算」を逆元の概念で扱います。 $\pmod{m}$ において $c$ の逆元とは、$cx \equiv 1 \pmod{m}$ を満たす $x$ のことです。
たとえば $\pmod{7}$ で $3$ の逆元は $5$ です（$3 \times 5 = 15 \equiv 1 \pmod{7}$）。 $c$ で割ることは、$c$ の逆元を掛けることと同じです。
逆元が存在するのは $\gcd(c, m) = 1$ のときに限ります。 これが「互いに素なら割れる」の数学的な根拠です。 暗号理論（RSA暗号など）では、この逆元の計算が鍵の生成に使われています。
合同式の最も典型的な応用は、大きなべき乗を $m$ で割った余りを求める問題です。 「$7^{100}$ を $5$ で割った余りを求めよ」── こんな問題をどう解くか、考えてみましょう。
$7^{100}$ を直接計算するのは不可能です。しかし、合同式を使えば余りだけを追跡できます。
$n^1, n^2, n^3, \ldots$ を $m$ で割った余りの列を考えると、この列は必ず周期的になります。
理由は簡単です。余りは $0, 1, 2, \ldots, m-1$ の $m$ 種類しかないので、 $m + 1$ 個以上の項があれば、どこかで同じ余りが再び現れます。 同じ余りが現れたら、そこから先は同じパターンの繰り返しになります。
この周期を見つければ、$n^{100}$ でも $n^{1000}$ でも、余りを簡単に求められるのです。
Step 1：$7 \equiv 2 \pmod{5}$ なので、$7^{100} \equiv 2^{100} \pmod{5}$。
Step 2：$2$ のべき乗を $\pmod{5}$ で追跡する。
$2^1 \equiv 2$、$2^2 \equiv 4$、$2^3 \equiv 8 \equiv 3$、$2^4 \equiv 16 \equiv 1 \pmod{5}$
Step 3：$2^4 \equiv 1 \pmod{5}$ が見つかった! 周期は $4$。
$100 = 4 \times 25$ なので $2^{100} = (2^4)^{25} \equiv 1^{25} = 1 \pmod{5}$
結論：$7^{100}$ を $5$ で割った余りは $\mathbf{1}$。
ポイントは、$n^k \equiv 1 \pmod{m}$ となる $k$（位数と呼ばれます）を見つけることです。 $1$ になれば、そこから先は元に戻って繰り返します。
べき乗の余りを効率よく求めるテクニックをまとめます。
1. 底をまず $m$ で割った余りに「縮める」（$n \equiv r \pmod{m}$）
2. $r, r^2, r^3, \ldots$ の余りを順に計算し、$r^k \equiv 1 \pmod{m}$ となる $k$ を見つける
3. 指数を $k$ で割る：$\text{(指数)} = k \times q + s$ として $n^{\text{指数}} \equiv r^s \pmod{m}$
$r$ と $m$ が互いに素でないとき、$r^k \equiv 1 \pmod{m}$ となる $k$ は存在しません。
✕ 誤：$2^n$ を $6$ で割った余りで $2^k \equiv 1 \pmod{6}$ を探す → 見つからない
○ 正：$2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 2$, $2^4 \equiv 4$, $\ldots \pmod{6}$。 余りは $2, 4, 2, 4, \ldots$ と周期 $2$ で繰り返しますが、$1$ にはなりません。 $\gcd(2, 6) = 2 \neq 1$ だからです。
この場合でも余りは周期的なので、周期さえ見つければ問題は解けます。 ただし $r^k \equiv 1$ の形にはなりません。
時計は $\pmod{12}$ の合同式です。今 $9$ 時で、$5$ 時間後は $9 + 5 = 14 \equiv 2 \pmod{12}$ で $2$ 時。 曜日は $\pmod{7}$ の合同式で、「今日は水曜日、$100$ 日後は何曜日?」は $100 \equiv 2 \pmod{7}$ なので金曜日です。
このように、日常の周期的な現象はすべて合同式で表現できます。 合同式は「周期的な構造を扱う言語」なのです。
Section 3で「$n^k \equiv 1 \pmod{m}$ となる $k$ を見つける」という話をしました。 法 $m$ が素数のとき、この $k$ について驚くほど美しい定理があります。 それがフェルマーの小定理です。
$p$ を素数、$a$ を $p$ と互いに素な整数とするとき：
$$a^{p-1} \equiv 1 \pmod{p}$$
同値な表現として、すべての整数 $a$ に対して $a^p \equiv a \pmod{p}$ が成り立つ。
具体例で確認してみましょう。$p = 5$, $a = 3$ のとき：
$$3^{5-1} = 3^4 = 81 = 16 \times 5 + 1 \equiv 1 \pmod{5} \quad \checkmark$$$p = 7$, $a = 2$ のとき：
$$2^{7-1} = 2^6 = 64 = 9 \times 7 + 1 \equiv 1 \pmod{7} \quad \checkmark$$Section 3で「$a^k \equiv 1 \pmod{m}$ となる $k$ を見つける」という作業をしました。 法 $m$ が素数 $p$ のとき、フェルマーの小定理は$k = p - 1$ で必ず $1$ に戻ることを保証します。
つまり、「$p - 1$ 乗すれば必ず $1$ になる」というのは、余りの周期が $p - 1$ の約数であることを意味します。 実際の周期はもっと短いかもしれませんが、$p - 1$ は周期の上限として使えるのです。
これにより、法が素数のときは周期を探す手間が省けることがあります。
$p$ を素数、$a$ を $p$ と互いに素な整数とする。$1, 2, 3, \ldots, p-1$ の各要素に $a$ を掛けた
$$a \cdot 1, \quad a \cdot 2, \quad a \cdot 3, \quad \ldots, \quad a \cdot (p-1)$$
を $\pmod{p}$ で考える。これら $p - 1$ 個の数を $p$ で割った余りは、$1, 2, \ldots, p-1$ の並べ替えになっていることを示す。
（1）どの余りも $0$ にならない：$a \cdot k \equiv 0 \pmod{p}$ なら $p \mid ak$。$\gcd(a, p) = 1$ なので $p \mid k$。しかし $1 \leq k \leq p-1$ より $p \nmid k$。矛盾。
（2）異なる $k$ からは異なる余りが出る：$a \cdot k_1 \equiv a \cdot k_2 \pmod{p}$ とすると $a(k_1 - k_2) \equiv 0 \pmod{p}$。$\gcd(a, p) = 1$ なので $k_1 \equiv k_2 \pmod{p}$。$1 \leq k_1, k_2 \leq p-1$ より $k_1 = k_2$。
以上より、$\{a \cdot 1, a \cdot 2, \ldots, a \cdot (p-1)\}$ を $\pmod{p}$ で見ると $\{1, 2, \ldots, p-1\}$ の並べ替え。
よって全部を掛け合わせると：
$$(a \cdot 1)(a \cdot 2) \cdots (a \cdot (p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}$$
$$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$$
$(p-1)!$ と $p$ は互いに素（$p$ は素数なので $(p-1)!$ の因数にならない）なので、両辺を $(p-1)!$ で割れる：
$$a^{p-1} \equiv 1 \pmod{p}$$
$5$ は素数で、$\gcd(7, 5) = 1$ なのでフェルマーの小定理が使える。
$7^{5-1} = 7^4 \equiv 1 \pmod{5}$
$203 = 4 \times 50 + 3$ なので：
$7^{203} = (7^4)^{50} \cdot 7^3 \equiv 1^{50} \cdot 7^3 \equiv 7^3 \pmod{5}$
$7 \equiv 2 \pmod{5}$ より $7^3 \equiv 2^3 = 8 \equiv 3 \pmod{5}$
答え：余りは $\mathbf{3}$。
✕ 誤：$a^{m-1} \equiv 1 \pmod{m}$ はどんな $m$ でも成り立つ
○ 正：フェルマーの小定理は法 $p$ が素数のときにのみ成り立ちます。 合成数 $m$ に対しては一般に $a^{m-1} \equiv 1 \pmod{m}$ は成り立ちません。
たとえば $m = 4$（合成数）, $a = 2$：$2^3 = 8 \equiv 0 \pmod{4}$（$1$ ではない）。
合成数の場合は、オイラーの定理（$a^{\varphi(m)} \equiv 1 \pmod{m}$、$\varphi$ はオイラー関数）が一般化になりますが、これは大学の範囲です。
インターネットで使われるRSA暗号は、フェルマーの小定理（とその一般化であるオイラーの定理）に基づいています。 大きな素数 $p, q$ の積 $n = pq$ に対して、$m^{ed} \equiv m \pmod{n}$ という関係式が暗号化と復号に使われます。
この関係式が成り立つ根拠がフェルマーの小定理です。 17世紀にフェルマーが発見した純粋数学の定理が、21世紀のインターネットセキュリティを支えているのは、数学の不思議な力です。
合同式は整数論の多くの概念を「余りの言語」で統一的に扱う道具です。 全体像を整理しましょう。
| パターン | 問題の特徴 | 解法のポイント |
|---|---|---|
| A：余りの計算 | $n^k$ を $m$ で割った余りを求める | 底を余りに縮めてからべき乗の周期を見つける |
| B：整除の証明 | $n^k - a$ が $m$ の倍数であることを示す | $n^k \equiv a \pmod{m}$ を示す |
| C：余りの分類 | $n^2$ や $n^3$ の余りのパターンを調べる | $n \equiv 0, 1, \ldots, m-1$ を全部試す |
| D：合同方程式 | $ax \equiv b \pmod{m}$ を解く | $\gcd(a, m) = 1$ なら逆元を使う |
| E：フェルマー応用 | 大きなべき乗の余り（法が素数） | $a^{p-1} \equiv 1$ で指数を縮める |
Q1. $47 \equiv \text{?} \pmod{7}$ の $\text{?}$ に入る $0$ 以上 $7$ 未満の整数を答えてください。
Q2. $a \equiv b \pmod{m}$, $c \equiv d \pmod{m}$ のとき、$ac \equiv \text{?} \pmod{m}$ ですか。
Q3. $6a \equiv 6b \pmod{9}$ から $a \equiv b \pmod{9}$ は導けますか？ 理由も述べてください。
Q4. $3^{20}$ を $5$ で割った余りを求めてください。
Q5. フェルマーの小定理を使うための2つの条件は何ですか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
$2^{50}$ を $7$ で割った余りを求めよ。
余り $4$
方針：$2$ のべき乗を $\pmod{7}$ で追跡し、周期を見つける。
$2^1 \equiv 2$, $2^2 \equiv 4$, $2^3 \equiv 1 \pmod{7}$
$2^3 \equiv 1 \pmod{7}$ より周期は $3$。
$50 = 3 \times 16 + 2$ なので $2^{50} = (2^3)^{16} \cdot 2^2 \equiv 1^{16} \cdot 4 = 4 \pmod{7}$
よって余りは $4$。
$n$ を整数とするとき、$n^3 - n$ は $6$ の倍数であることを証明せよ。
（証明は解説を参照）
方針：$n^3 - n = n(n-1)(n+1)$ と因数分解してもよいが、合同式で示す方法を紹介する。
$6 = 2 \times 3$ なので、$n^3 - n$ が $2$ の倍数かつ $3$ の倍数であることを示せばよい。
$\pmod{2}$ の確認：$n \equiv 0$ のとき $n^3 - n \equiv 0$。$n \equiv 1$ のとき $1 - 1 = 0$。
よって $n^3 - n \equiv 0 \pmod{2}$。✓
$\pmod{3}$ の確認：$n \equiv 0$ のとき $0 - 0 = 0$。$n \equiv 1$ のとき $1 - 1 = 0$。$n \equiv 2$ のとき $8 - 2 = 6 \equiv 0$。
よって $n^3 - n \equiv 0 \pmod{3}$。✓
$n^3 - n$ は $2$ の倍数かつ $3$ の倍数で、$\gcd(2, 3) = 1$ なので $6$ の倍数。（証明終）
※ 別解として、フェルマーの小定理より $n^3 \equiv n \pmod{3}$（$p = 3$）を使えば $\pmod{3}$ の部分は一発です。
$3^{100} + 5^{100}$ を $8$ で割った余りを求めよ。
余り $2$
方針：$3^{100}$ と $5^{100}$ をそれぞれ $\pmod{8}$ で求めて足す。
$3^{100} \pmod{8}$：$3^1 \equiv 3$, $3^2 \equiv 9 \equiv 1 \pmod{8}$。周期 $2$。$100 = 2 \times 50$ より $3^{100} \equiv 1 \pmod{8}$。
$5^{100} \pmod{8}$：$5^1 \equiv 5$, $5^2 \equiv 25 \equiv 1 \pmod{8}$。周期 $2$。$100 = 2 \times 50$ より $5^{100} \equiv 1 \pmod{8}$。
$3^{100} + 5^{100} \equiv 1 + 1 = 2 \pmod{8}$
よって余りは $2$。
$n$ を $5$ と互いに素な正の整数とするとき、$n^4 - 1$ は $5$ の倍数であることを証明せよ。
また、$7^{203}$ を $5$ で割った余りを求めよ。
（前半の証明は解説を参照）。$7^{203}$ を $5$ で割った余りは $3$。
前半の方針：フェルマーの小定理を適用する。
$5$ は素数で、$n$ と $5$ は互いに素なので、フェルマーの小定理より：
$$n^{5-1} = n^4 \equiv 1 \pmod{5}$$
すなわち $n^4 - 1 \equiv 0 \pmod{5}$、つまり $n^4 - 1$ は $5$ の倍数。（証明終）
後半の方針：$\gcd(7, 5) = 1$ なのでフェルマーの小定理が使える。
$7^4 \equiv 1 \pmod{5}$。$203 = 4 \times 50 + 3$ より：
$7^{203} = (7^4)^{50} \cdot 7^3 \equiv 1^{50} \cdot 7^3 = 7^3 \pmod{5}$
$7 \equiv 2 \pmod{5}$ より $7^3 \equiv 2^3 = 8 \equiv 3 \pmod{5}$。
よって余りは $3$。