中国剰余定理と連立合同式

互いに素な法の連立合同式を中国剰余定理で 1 つの合同式 $x \equiv c (mod M)$ にまとめられる。法が互いに素でないときは、解をもつ条件 $a_{i} \equiv a_{j} (mod g cd (m_{i}, m_{j}))$ を確かめ、法 $lcm (m_{1}, \dots, m_{k})$ での解を求めて、範囲内の解の個数や和を求められる

前提

互いに素な法への分解（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

この技能までの道筋（24 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
互いに素な法への分解（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）

説明

いくつかの合同式 $x \equiv a_{1} (mod m_{1}), \dots, x \equiv a_{k} (mod m_{k})$ を同時に満たす整数 $x$ を、1 つの合同式 $x \equiv c (mod M)$ にまとめる技能です。法がどの 2 つも互いに素なら、解は必ずあり、法 $M = m_{1} m_{2} \dots m_{k}$ でただ 1 つに決まります（中国剰余定理）。法が互いに素でないときは、まず解があるかを判定します。解があれば、法 $lcm (m_{1}, \dots, m_{k})$ でただ 1 つに決まります。解が「 $M$ おきに 1 つずつ並ぶ数」だとわかるので、範囲内の解の個数や和も数えられます。

なぜそうしてよいのか

【互いに素な場合】 $M = m_{1} \dots m_{k}$ 、 $M_{i} = M / m_{i}$ とおきます。 $M_{i}$ は $m_{i}$ 以外の法をすべて掛けた数です。法がどの 2 つも互いに素なので $g cd (M_{i}, m_{i}) = 1$ です。よって拡張ユークリッドの互除法で、 $M_{i} y_{i} \equiv 1 (mod m_{i})$ となる $y_{i}$ （ $M_{i}$ の逆元）が求まります。 $e_{i} = M_{i} y_{i}$ とおくと、 $e_{i}$ を $m_{i}$ で割った余りは $1$ です。 $j \neq = i$ のときは $M_{i}$ が $m_{j}$ の倍数なので、 $e_{i}$ を $m_{j}$ で割った余りは $0$ です。つまり $e_{i}$ は「 $i$ 番目の条件だけに $1$ を出すスイッチ」です。したがって $x = a_{1} e_{1} + \dots + a_{k} e_{k}$ を法 $m_{i}$ で見ると $a_{i} \cdot 1$ 以外の項が消え、すべての式 $x \equiv a_{i} (mod m_{i})$ が成り立ちます。次に、解がただ 1 つであることを示します。 $x, x^{'}$ がどちらも解なら、 $x - x^{'}$ はすべての $m_{i}$ で割り切れます。前提の技能（互いに素な法への分解）より、どの 2 つも互いに素な数すべてで割り切れることは、その積 $M$ で割り切れることと同じです。よって $x \equiv x^{'} (mod M)$ です。逆に、解に $M$ の倍数を足しても解のままです。

【互いに素でない 2 式】 $x \equiv a_{1} (mod m_{1})$ 、 $x \equiv a_{2} (mod m_{2})$ を考え、 $d = g cd (m_{1}, m_{2})$ とおきます。 $d$ は $m_{1}$ も $m_{2}$ も割り切るので、解 $x$ があれば法 $d$ で $a_{1} \equiv x \equiv a_{2}$ です。よって $a_{1} \equiv a_{2} (mod d)$ が必要です。逆にこの条件が成り立つとします。第 1 式の解は $x = a_{1} + m_{1} t$ （ $t$ は整数）と書けるので、これを第 2 式に代入して $m_{1} t \equiv a_{2} - a_{1} (mod m_{2})$ を解きます。 $m_{1} t - (a_{2} - a_{1}) = d (\frac{m _{1}}{d} t - \frac{a _{2} - a _{1}}{d})$ 、 $m_{2} = d \cdot \frac{m _{2}}{d}$ です。そのため、 $m_{2}$ がこれを割り切ることは、 $\frac{m _{2}}{d}$ がかっこの中を割り切ることと同じです。つまり、両辺と法を $d$ で割った $\frac{m _{1}}{d} t \equiv \frac{a _{2} - a _{1}}{d} (mod \frac{m _{2}}{d})$ と同値です。ここで $g cd (\frac{m _{1}}{d}, \frac{m _{2}}{d}) = 1$ です。もし両方を割る $g > 1$ があれば、 $d g$ が $m_{1}, m_{2}$ の公約数となり、 $d$ が最大であることに反するからです。よって $\frac{m _{1}}{d}$ には法 $\frac{m _{2}}{d}$ での逆元 $u$ があります。両辺に $u$ を掛けると $t \equiv u \cdot \frac{a _{2} - a _{1}}{d} (mod \frac{m _{2}}{d})$ となり、 $t$ は法 $\frac{m _{2}}{d}$ でただ 1 つに決まります。その値を $t_{0}$ とすると $t = t_{0} + \frac{m _{2}}{d} s$ （ $s$ は整数）です。これを代入すると $x = a_{1} + m_{1} t_{0} + \frac{m _{1} m _{2}}{d} s$ になります。 $\frac{m _{1} m _{2}}{d} = lcm (m_{1}, m_{2})$ なので、解全体は $x \equiv a_{1} + m_{1} t_{0} (mod lcm (m_{1}, m_{2}))$ です。

【3 式以上】2 式ずつまとめていきます。まとめるたびに、まとめた式と次の式の間で上の条件を確かめれば、どの段階でも確実に正しく判定できます。実は、最初にすべての組 $i, j$ で $a_{i} \equiv a_{j} (mod g cd (m_{i}, m_{j}))$ が成り立っていれば、途中で行き詰まることはありません。理由を示します。第 1・第 2 式をまとめた解を $x \equiv c (mod L)$ 、 $L = lcm (m_{1}, m_{2})$ とし、 $g_{1} = g cd (m_{1}, m_{3})$ 、 $g_{2} = g cd (m_{2}, m_{3})$ とおきます。 $c \equiv a_{1} (mod m_{1})$ なので $c \equiv a_{1} \equiv a_{3} (mod g_{1})$ です。同様に $c \equiv a_{3} (mod g_{2})$ です。よって $c - a_{3}$ は $g_{1}, g_{2}$ の公倍数なので、 $lcm (g_{1}, g_{2})$ の倍数です。一方、各素数 $p$ について、 $p$ が $m_{1}, m_{2}, m_{3}$ を割る回数を $e_{1}, e_{2}, e_{3}$ とします。このとき $g cd (L, m_{3})$ の指数は $min (max (e_{1}, e_{2}), e_{3})$ 、 $lcm (g_{1}, g_{2})$ の指数は $max (min (e_{1}, e_{3}), min (e_{2}, e_{3}))$ です。 $e_{1} \geq e_{2}$ ならどちらも $min (e_{1}, e_{3})$ になり、 $e_{1} < e_{2}$ でも同様に等しくなります。よって $g cd (L, m_{3}) = lcm (g_{1}, g_{2})$ です。したがって $c \equiv a_{3} (mod g cd (L, m_{3}))$ が成り立ち、第 3 式とも必ずまとめられます。第 4 式以降についても同じ議論が使えます。以上から、すべての組での条件が、解をもつための必要十分条件です。

手順

法がどの 2 つも互いに素かを調べる（全体の $g cd$ が $1$ でも、ある 2 つが互いに素でなければ「どの 2 つも互いに素」ではない）。互いに素でない組 $m_{i}, m_{j}$ があれば $a_{i} \equiv a_{j} (mod g cd (m_{i}, m_{j}))$ を確かめ、1 組でも成り立たなければ「解なし」と判定する
（互いに素な場合） $M = m_{1} m_{2} \dots m_{k}$ と $M_{i} = M / m_{i}$ を計算する
各 $i$ について $M_{i} y_{i} \equiv 1 (mod m_{i})$ となる $y_{i}$ を求める。まず $M_{i}$ を $m_{i}$ で割った余りに直し、小さければ試して求め、大きければ拡張ユークリッドの互除法で求める
$x \equiv a_{1} M_{1} y_{1} + \dots + a_{k} M_{k} y_{k} (mod M)$ を計算し、 $0 \leq c < M$ に直して $x \equiv c (mod M)$ とする
（互いに素でない場合） $d = g cd (m_{1}, m_{2})$ とし、 $x = a_{1} + m_{1} t$ を第 2 式に代入して $m_{1} t \equiv a_{2} - a_{1} (mod m_{2})$ とする。両辺と法を $d$ で割って $\frac{m _{1}}{d} t \equiv \frac{a _{2} - a _{1}}{d} (mod \frac{m _{2}}{d})$ とする。 $\frac{m _{1}}{d}$ の法 $\frac{m _{2}}{d}$ での逆元 $u$ を求め、 $t_{0} \equiv u \cdot \frac{a _{2} - a _{1}}{d} (mod \frac{m _{2}}{d})$ とする。これで $x \equiv a_{1} + m_{1} t_{0} (mod lcm (m_{1}, m_{2}))$ が得られる。式が 3 つ以上あれば、まとめた式と次の式で手順 1 の確認とこの手順をくり返す
範囲内の解を問われたら、解が $c, c + M, c + 2 M, \dots$ （互いに素でない場合は $M$ を $lcm$ に置きかえる）と等間隔に並ぶことを使って、個数や和を数える

例題

$x \equiv 2 (mod 4)$ 、 $x \equiv 3 (mod 5)$ 、 $x \equiv 5 (mod 7)$ をすべて満たす最小の正の整数 $x$ を求めよ。

例題の解答

手順 1： $g cd (4, 5) = g cd (4, 7) = g cd (5, 7) = 1$ で、 $4, 5, 7$ はどの 2 つも互いに素である。よって中国剰余定理がそのまま使える。

手順 2： $M = 4 \cdot 5 \cdot 7 = 140$ である。 $M_{1} = 140/4 = 35$ 、 $M_{2} = 140/5 = 28$ 、 $M_{3} = 140/7 = 20$ となる。

手順 3：逆元を求める。
- $35 \equiv 3 (mod 4)$ で、 $3 \cdot 3 = 9 \equiv 1 (mod 4)$ なので $y_{1} = 3$ 。
- $28 \equiv 3 (mod 5)$ で、 $3 \cdot 2 = 6 \equiv 1 (mod 5)$ なので $y_{2} = 2$ 。
- $20 \equiv 6 (mod 7)$ で、 $6 \cdot 6 = 36 \equiv 1 (mod 7)$ なので $y_{3} = 6$ 。

手順 4： $x \equiv 2 \cdot 35 \cdot 3 + 3 \cdot 28 \cdot 2 + 5 \cdot 20 \cdot 6 = 210 + 168 + 600 = 978 (mod 140)$ である。 $978 = 6 \cdot 140 + 138$ なので $x \equiv 138 (mod 140)$ となる。

検算： $138 = 4 \cdot 34 + 2$ 、 $138 = 5 \cdot 27 + 3$ 、 $138 = 7 \cdot 19 + 5$ で、3 つの条件をすべて満たす。

手順 6：解は $\dots, - 2, 138, 278, \dots$ と $140$ おきに並ぶ。 $138$ の 1 つ前の解 $138 - 140 = - 2$ は正でない。よって最小の正の整数は $138$ である。

答え: $138$

よくある誤り

全体の最大公約数が $1$ であることを「どの 2 つも互いに素」と取り違え、法をそのまま掛けてしまう誤り。たとえば $6, 10, 15$ は全体の $g cd$ が $1$ だが、 $g cd (6, 10) = 2$ 、 $g cd (6, 15) = 3$ 、 $g cd (10, 15) = 5$ である。正しくは、各組で $a_{i} \equiv a_{j} (mod g cd (m_{i}, m_{j}))$ を確かめる。解の法も $6 \cdot 10 \cdot 15 = 900$ ではなく $lcm (6, 10, 15) = 30$ である。
解があるかを確かめずに計算を進めてしまう誤り。たとえば $x \equiv 1 (mod 4)$ 、 $x \equiv 2 (mod 6)$ では、 $g cd (4, 6) = 2$ について $1 \neq \equiv 2 (mod 2)$ である（ $x$ が奇数かつ偶数になってしまう）。正しくは「解なし」と判定する。
逆元 $y_{i}$ を掛け忘れて $x \equiv \sum a_{i} M_{i}$ としてしまう誤り。例題では $2 \cdot 35 + 3 \cdot 28 + 5 \cdot 20 = 254 \equiv 114 (mod 140)$ となるが、 $114 \equiv 4 (mod 5)$ なので条件を満たさない。正しくは、 $M_{i} y_{i} \equiv 1 (mod m_{i})$ となる $y_{i}$ を掛けて $x \equiv \sum a_{i} M_{i} y_{i} (mod M)$ とする。
互いに素でない場合に、両辺だけを $d$ で割って法を割り忘れる誤り。たとえば $x \equiv 1 (mod 4)$ 、 $x \equiv 3 (mod 6)$ で $x = 1 + 4 t$ を代入すると $4 t \equiv 2 (mod 6)$ になる。これを $2 t \equiv 1 (mod 6)$ とすると、左辺がいつも偶数になるので「解なし」と誤って判定してしまう。正しくは、法も $2$ で割って $2 t \equiv 1 (mod 3)$ とする。 $2$ の法 $3$ での逆元は $2$ なので $t \equiv 2 (mod 3)$ となり、 $x \equiv 1 + 4 \cdot 2 = 9 (mod 12)$ が得られる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

中国剰余定理と連立合同式

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題