中国剰余定理はなぜ「合体」できるのか ― 連立合同式の魔法

CRT を分割統治の整数論版として捉え，環の同型 Z/mnZ ≅ Z/mZ × Z/nZ の直感的意味と，Garner のアルゴリズムによる競プロ応用までを解説します．

2026年2月27日

中国剰余定理（CRT）は，紀元3世紀の中国の数学書『孫子算経』に起源をもつ古い定理ですが，現代でも暗号理論や競技プログラミングで活躍する強力なツールです．連立合同式を「合体」して1つの合同式にする ― この魔法のような操作の背後にある構造を解き明かします．

1 孫子の問題 ― 古代からの出発

例 1 (孫子算経の問題).

ある数は，3 で割ると 2 余り，5 で割ると 3 余り，7 で割ると 2 余ります．この数は何でしょうか？

つまり連立合同式

x \equiv 2 (mod 3), x \equiv 3 (mod 5), x \equiv 2 (mod 7)

を解きます．答えは

x \equiv 23 (mod 105)

です（

105 = 3 \times 5 \times 7

）．

2 中国剰余定理の主張

定理 2 (中国剰余定理).

m_{1}, m_{2}, \dots, m_{k}

が対ごとに互いに素（

i \neq = j

のとき

g cd (m_{i}, m_{j}) = 1

）であるとき，連立合同式

x \equiv a_{1} (mod m_{1}), x \equiv a_{2} (mod m_{2}), \dots, x \equiv a_{k} (mod m_{k})

は

mod M = m_{1} m_{2} \dots m_{k}

で唯一の解をもちます．

注意 3.

CRT が言っていることを一言でまとめると：互いに素な法での余りの組は，それらの積を法とする1つの余りと同じ情報をもつ，ということです．

3 構成的証明 ― 解を実際に作る

証明.

M = m_{1} m_{2} \dots m_{k}

とし，

M_{i} = M / m_{i}

とします．

g cd (M_{i}, m_{i}) = 1

（

M_{i}

は

m_{i}

以外のすべての法の積）なので，

M_{i} t_{i} \equiv 1 (mod m_{i})

となる

t_{i}

が存在します（拡張ユークリッドの互除法で計算）．

x = i = 1 \sum k a_{i} M_{i} t_{i}

とおくと，

j \neq = i

のとき

m_{i} ∣ M_{j}

なので

M_{j} t_{j} \equiv 0 (mod m_{i})

，また

M_{i} t_{i} \equiv 1 (mod m_{i})

より，

x \equiv a_{i} \cdot 1 + j \neq = i \sum a_{j} \cdot 0 = a_{i} (mod m_{i})

が成り立ちます．

一意性：

x, x^{'}

がともに解なら，各

m_{i} ∣ (x - x^{'})

．

m_{i}

が対ごとに互いに素なので

M ∣ (x - x^{'})

，つまり

x \equiv x^{'} (mod M)

． □

例 4 (孫子の問題の解).

m_{1} = 3, m_{2} = 5, m_{3} = 7

，

M = 105

．

$M_{1} = 35$ ， $35 t_{1} \equiv 1 (mod 3)$ → $t_{1} = 2$ （ $35 \times 2 = 70 \equiv 1 (mod 3)$ ）
$M_{2} = 21$ ， $21 t_{2} \equiv 1 (mod 5)$ → $t_{2} = 1$ （ $21 \equiv 1 (mod 5)$ ）
$M_{3} = 15$ ， $15 t_{3} \equiv 1 (mod 7)$ → $t_{3} = 1$ （ $15 \equiv 1 (mod 7)$ ）

x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233 \equiv 23 (mod 105)

．

4 環の直積分解 ― 代数的な意味

CRT は代数の言葉で次のように述べられます．

定理 5 (環の同型).

g cd (m, n) = 1

のとき，環の同型

Z / mn Z ≅ Z / m Z \times Z / n Z

が成り立ちます．同型写像は

x mod mn \mapsto (x mod m, x mod n)

です．

注意 6.

この同型は，「

mn

で割った余り」と「

m

で割った余りと

n

で割った余りの組」がまったく同じ情報であることを意味します．

mn

通りの余りと

m \times n

通りの余りの組が，1対1に対応するのです．

これは分割統治の整数論版です．大きな法

mn

での計算を，小さな法

m, n

での計算に分割し，後で合体するのです．

5 Garner のアルゴリズム

CRT の構成的証明による直接計算は， $M_{i}$ が非常に大きくなりオーバーフローの危険があります．Garner のアルゴリズムはこの問題を回避します．

注意 7 (Garner のアイデア).

x

を混合基数表現

x = r_{1} + r_{2} m_{1} + r_{3} m_{1} m_{2} + \dots + r_{k} m_{1} m_{2} \dots m_{k - 1}

で表します．

r_{1}, r_{2}, \dots, r_{k}

を順に求めていきます：

$x \equiv a_{1} (mod m_{1})$ より $r_{1} = a_{1} mod m_{1}$
$x \equiv a_{2} (mod m_{2})$ に $x = r_{1} + r_{2} m_{1} + \dots$ を代入すると $r_{2} m_{1} \equiv a_{2} - r_{1} (mod m_{2})$ ，つまり $r_{2} \equiv (a_{2} - r_{1}) m_{1}^{- 1} (mod m_{2})$
以降同様に $r_{i}$ を $mod m_{i}$ で求めます

各ステップで

mod m_{i}

の範囲で計算するので，中間値が大きくなりません．

6 競プロ応用 ― 大きな mod 下での計算

例 8 (異なる素数 mod での計算の合体).

組合せ数

(k n)

を

m = p_{1} p_{2}

で割った余りを求めたいが，

m

が素数ではないとします．

(k n) mod p_{1}

と

(k n) mod p_{2}

をそれぞれ計算し，CRT で合体すれば

mod m

での値が得られます．

注意 9 (AtCoder での典型パターン).

以下のような場面で CRT が使えます：

複数の素数 mod での計算結果を1つにまとめる
答えが非常に大きいが，複数の小さな mod での値から復元したい
$mod m$ で $m$ が素数でないとき，素因数分解して各素数 mod で計算する

7 まとめ

CRT：互いに素な法での余りの組は，積を法とする余りと1対1に対応します
代数的には $Z / mn Z ≅ Z / m Z \times Z / n Z$ （分割統治の代数版）
構成的証明により，解を明示的に計算できます
Garner のアルゴリズムでオーバーフローを回避しながら実装できます

次の記事では， $mod p$ の世界で「平方数」がどう振る舞うか ― 二次剰余の不思議な世界に踏み込みます．

整数論代数学教科書の行間

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

中国剰余定理はなぜ「合体」できるのか ― 連立合同式の魔法

1 孫子の問題 ― 古代からの出発

2 中国剰余定理の主張

3 構成的証明 ― 解を実際に作る

4 環の直積分解 ― 代数的な意味

5 Garner のアルゴリズム

6 競プロ応用 ― 大きな mod 下での計算

7 まとめ

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ