中国剰余定理と応用 ― 連立合同式と環の直積分解

中国剰余定理を環の同型写像として代数的に証明する．一般の場合（$\gcd \neq 1$）への拡張，Garnerのアルゴリズム，$\varphi$の乗法性のCRTによる証明，および競技プログラミングへの応用を扱う．

2026年2月27日

1 中国剰余定理の主張

定理 1 (中国剰余定理（CRT）).

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

が対ごとに互いに素（

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

，

i \neq = j

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

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}

でただ一つの解を持つ．

証明.

存在：各

i

に対して

M_{i} = M / m_{i}

とおく．

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

（

i \neq = j

）より

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

なので，ベズーの等式から

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

なる整数

t_{i}

が存在する．

e_{i} = M_{i} t_{i}

とおくと

e_{i} \equiv 1 (mod m_{i})

かつ

j \neq = i

のとき

m_{j} ∣ M_{i}

より

e_{i} \equiv 0 (mod m_{j})

．

x = \sum_{i = 1}^{k} a_{i} e_{i}

とおけば各

i

に対して

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

．

一意性：

x_{1}, x_{2}

がともに連立合同式の解とすると，すべての

i

に対して

m_{i} ∣ (x_{1} - x_{2})

．

m_{i}

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

M = m_{1} m_{2} \dots m_{k} ∣ (x_{1} - x_{2})

，すなわち

x_{1} \equiv x_{2} (mod M)

． □

2 代数的証明：環の同型

定理 2 (CRT の環論的定式化).

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

が対ごとに互いに素であるとき，

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

として環の同型

Φ : Z / M Z \sim Z / m_{1} Z \times Z / m_{2} Z \times \dots \times Z / m_{k} Z

が

Φ (\overset{x}{ˉ}) = (\overset{x}{ˉ}_{1}, \dots, \overset{x}{ˉ}_{k})

（

\overset{x}{ˉ}_{i}

は

x mod m_{i}

）により与えられる．

証明.

Φ

が環準同型であることは明らか（和と積を保つ）．

単射性：

Φ (\overset{x}{ˉ}) = \overset{ˉ}{0}

とすると

m_{i} ∣ x

がすべての

i

で成立．

m_{i}

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

M ∣ x

，すなわち

\overset{x}{ˉ} = \overset{ˉ}{0}

Z / M Z

．

全射性：

M_{i} = M / m_{i}

とおく．

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

なので

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

なる

t_{i}

が存在する．

e_{i} = M_{i} t_{i}

とおくと

e_{i} \equiv 1 (mod m_{i})

かつ

j \neq = i

のとき

e_{i} \equiv 0 (mod m_{j})

．任意の

(a_{1}, \dots, a_{k})

に対して

x = \sum_{i = 1}^{k} a_{i} e_{i}

が

Φ (\overset{x}{ˉ}) = (\overset{a}{ˉ}_{1}, \dots, \overset{a}{ˉ}_{k})

を満たす．

有限集合間の単射は全射でもあるので（

∣ Z / M Z ∣ = M = \prod m_{i}

），

Φ

は全単射． □

3 解の具体的構成

例 3.

x \equiv 2 (mod 3)

，

x \equiv 3 (mod 5)

，

x \equiv 2 (mod 7)

を解く．

M = 105

，

M_{1} = 35

，

M_{2} = 21

，

M_{3} = 15

．

35 t_{1} \equiv 1 (mod 3)

より

t_{1} = 2

．

21 t_{2} \equiv 1 (mod 5)

より

t_{2} = 1

．

15 t_{3} \equiv 1 (mod 7)

より

t_{3} = 1

．

x \equiv 2 \cdot 70 + 3 \cdot 21 + 2 \cdot 15 = 233 \equiv 23 (mod 105)

．

4 一般の場合

定理 4.

連立合同式

x \equiv a_{1} (mod m_{1})

，

x \equiv a_{2} (mod m_{2})

が解を持つための必要十分条件は

g cd (m_{1}, m_{2}) ∣ (a_{1} - a_{2})

である．解が存在するとき，

mod lcm (m_{1}, m_{2})

でただ一つの解を持つ．

証明.

x = a_{1} + m_{1} k

と書くと第二式は

m_{1} k \equiv a_{2} - a_{1} (mod m_{2})

となる．一次合同式の解の存在条件より

g cd (m_{1}, m_{2}) ∣ (a_{2} - a_{1})

が必要十分．解の

mod

は

m_{1} \cdot m_{2} / g cd (m_{1}, m_{2}) = lcm (m_{1}, m_{2})

． □

5 Garner のアルゴリズム

注意 5.

Garner のアルゴリズムは CRT の解を混合基数表現

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

として構成する手法で，大きな

M

での直接計算を回避できる．各

r_{i}

は順次的に計算される：

r_{1} = a_{1} mod m_{1}

，

r_{2} = (a_{2} - r_{1}) \cdot m_{1}^{- 1} mod m_{2}

，以下同様．このアルゴリズムは各ステップで

mod m_{i}

の演算のみを行うため，多倍長整数の乗算を回避でき効率的である．

6 $φ$ の乗法性の CRT による証明

系 6.

g cd (m, n) = 1

ならば

φ (mn) = φ (m) φ (n)

．

証明.

CRT の環の同型

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

の単元群を取ると

(Z / mn Z)^{*} ≅ (Z / m Z)^{*} \times (Z / n Z)^{*}

．位数を取って

φ (mn) = φ (m) φ (n)

． □

注意 7.

CRT は競技プログラミングにおいても重要な道具である．例えば複数の素数

p_{1}, \dots, p_{k}

を法として計算した結果を CRT で統合することで，大きな値の正確な復元や

mod M

での計算が可能になる．

中国剰余定理と応用 ― 連立合同式と環の直積分解

1 中国剰余定理の主張

2 代数的証明：環の同型

3 解の具体的構成

4 一般の場合

5 Garner のアルゴリズム

6 $φ$ の乗法性の CRT による証明

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

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

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

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

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

1 中国剰余定理の主張

2 代数的証明：環の同型

3 解の具体的構成

4 一般の場合

5 Garner のアルゴリズム

6 φの乗法性の CRT による証明

関連する「教科書の行間」記事

あなたの専門知識を世界に発信しよう

Folio公式の他の記事

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

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

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

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

6 $φ$ の乗法性の CRT による証明