中国ちゅうごく剰余定理じょうよていり

date2026-07-14document_iddoc_16c1ea8122dd4f97dbc48e3dd5549d6cdescription互いに素な法で与えられた連立合同式を一意に解く—中国剰余定理の主張・構成的証明・逆元による解法・応用（調日算）を整理する。prerequisites合同式とmod演算の基本 / ユークリッドの互除法と一次不定方程式 / 整数の性質の基本type講義content_typelecturestatusactive

mathalgebranumber-theoryhighschoolundergraduatelecture

1導入どうにゅう

この講義こうぎでは、「互たがいに素そな法ほうで与あたえられた複数ふくすうの余あまり条件じょうけんは、合あわせた法ほうのもとで一意いちいの解かいを持もつ」ことを説明せつめいする。

「3 で割わると 2 余あまり、5 で割わると 3 余あまる整数せいすうは？」という問題もんだいを体系的たいけいてきに解とく道具どうぐが中国ちゅうごく剰余定理じょうよていり（CRT）である。中国ちゅうごくの古典こてん「孫子算経そんしさんけい」（3 〜 5 世紀せいき）に現あらわれたことから命名めいめい。

2用語ようごと定義ていぎ

2.1中国ちゅうごく剰余定理じょうよていりChinese Remainder Theorem

定理ていり： $m_{1}, m_{2}, \dots, m_{k}$ が互たがいに素そ（ $[PARSE ERROR: Undefined("Command(\"gcd\")")] (m_{i}, m_{j}) = 1$ 、 $i \neq j$ ）なとき、連立合同式れんりつごうどうしき

x \equiv a_{1} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{1}, x \equiv a_{2} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{2}, \dots, x \equiv a_{k} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{k}

は $M = m_{1} m_{2} \dots m_{k}$ を法ほうとして一意いちいの解かいを持もつ。

「中国ちゅうごく剰余定理じょうよていり」の命名めいめい：Chinese Remainder Theorem の訳やく。余あまり（remainder）= 剰余じょうよ。東洋とうようで独立どくりつに発見はっけんされた事実じじつを西洋せいようの数学者すうがくしゃが命名めいめいした。

定義ていぎが実現じつげんする性質せいしつ： $M$ の倍数ばいすう域いき（ $0 [PARSE ERROR: Undefined("Command(\"le\")")] x < M$ ）内うちにちょうど 1 つの解かいが存在そんざいする。

2.1.1一意性いちいせいの直観ちょっかん

法ほう	情報量じょうほうりょう
$x [PARSE ERROR: Undefined("Command(\"bmod\")")] m_{1}$	$m_{1}$ 通とおりの可能性かのうせいを 1 通とおりに限定げんてい
$x [PARSE ERROR: Undefined("Command(\"bmod\")")] m_{2}$	さらに $m_{2}$ 分ぶんの 1 に限定げんてい
$⋮$	$⋮$
全ぜん条件じょうけん	$M = m_{1} \dots m_{k}$ 通とおりのうち 1 通とおりに限定げんてい

3方針ほうしん

構成的証明こうせいてきしょうめい（解かいの構成こうせい）：各かく $i$ について $M_{i} = M / m_{i}$ （ $m_{i}$ 以外いがいの積せき）を作つくり、 $M_{i}$ の $[PARSE ERROR: Undefined("Command(\"bmod\")")] m_{i}$ における逆元ぎゃくげん $M_{i^{- 1}}$ を求もとめて

x \equiv \sum_{i = 1}^{k} a_{i} M_{i} M_{i^{- 1}} [PARSE ERROR: Undefined("Command(\"pmod\")")] M

と構成こうせいする。逆元ぎゃくげんの計算けいさんにユークリッド互除法ごじょほうを使用しようする。

4直感的ちょっかんてきな説明せつめい

「振ふり子こを 3 秒びょう周期しゅうきと 5 秒びょう周期しゅうきで同時どうじに鳴ならすと 15 秒びょう周期しゅうきで一致いっちする」。3 と 5 が互たがいに素そなので、 $[0, 15)$ のどの余あまり組くみみ合あわせもちょうど 1 回かい現あらわれる。CRT はこの「余あまり組くみみ合あわせ → 元もとの数かず」の逆引ぎゃくびきを与あたえる。

5厳密げんみつな説明せつめい

5.11. 存在そんざいの構成こうせい

各かく $i$ に対たいして $M_{i} = M / m_{i}$ と置おく。 $[PARSE ERROR: Undefined("Command(\"gcd\")")] (M_{i}, m_{i}) = 1$ （仮定かていより）なので、ユークリッド互除法ごじょほうで $M_{i^{- 1}} [PARSE ERROR: Undefined("Command(\"bmod\")")] m_{i}$ が存在そんざいする。

x_{0} = \sum_{i = 1}^{k} a_{i} M_{i} M_{i^{- 1}}

確認かくにん： $x_{0} [PARSE ERROR: Undefined("Command(\"bmod\")")] m_{i}$ を計算けいさんすると、 $j \neq i$ の項こうはすべて $m_{i}$ の倍数ばいすう（ $m_{i} ∣ M_{j}$ ）なので 0、 $i$ 番目ばんめの項こうは $a_{i} M_{i} M_{i^{- 1}} \equiv a_{i} \cdot 1 = a_{i} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{i}$ 。

5.22. 一意性いちいせいの証明しょうめい

$x_{0}$ と $x_{1}$ がともに全ぜん条件じょうけんを満みたすとき、 $x_{0} - x_{1} \equiv 0 [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{i}$ （ $\forall i$ ）。各かく $m_{i}$ が互たがいに素そなので $x_{0} - x_{1} \equiv 0 [PARSE ERROR: Undefined("Command(\"pmod\")")] M$ 。

5.33. 2変数にへんすうの具体的ぐたいてきな計算手順けいさんてじゅん

$x \equiv a_{1} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{1}$ 、 $x \equiv a_{2} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{2}$ （ $[PARSE ERROR: Undefined("Command(\"gcd\")")] (m_{1}, m_{2}) = 1$ ）を解とく：

方法ほうほう 1（代入法だいにゅうほう）： $x = a_{1} + m_{1} t$ と置おき、 $a_{1} + m_{1} t \equiv a_{2} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{2}$ から $t \equiv (a_{2} - a_{1}) m_{1^{- 1}} [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{2}$ を求もとめる。

方法ほうほう 2（構成公式こうせいこうしき）： $M = m_{1} m_{2}$ 、 $M_{1} = m_{2}$ 、 $M_{2} = m_{1}$ として上記じょうきの公式こうしきを適用てきようする。

例れい： $x \equiv 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 3$ 、 $x \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$

$M = 15$ 、 $M_{1} = 5$ 、 $M_{2} = 3$ 。

$5 \cdot M_{1^{- 1}} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 3 ⟹ 2 M_{1^{- 1}} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 3 ⟹ M_{1^{- 1}} = 2$

$3 \cdot M_{2^{- 1}} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5 ⟹ 3 M_{2^{- 1}} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5 ⟹ M_{2^{- 1}} = 2$

$x_{0} = 2 \cdot 5 \cdot 2 + 3 \cdot 3 \cdot 2 = 20 + 18 = 38 \equiv 8 [PARSE ERROR: Undefined("Command(\"pmod\")")] 15$

確認かくにん： $8 = 2 \cdot 3 + 2$ （ $[PARSE ERROR: Undefined("Command(\"bmod\")")] 3$ で 2）、 $8 = 1 \cdot 5 + 3$ （ $[PARSE ERROR: Undefined("Command(\"bmod\")")] 5$ で 3）。

5.44. 3変数さんへんすうの例れい

$x \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] 3$ 、 $x \equiv 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 4$ 、 $x \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ （ $[PARSE ERROR: Undefined("Command(\"gcd\")")] (3, 4) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (3, 5) = [PARSE ERROR: Undefined("Command(\"gcd\")")] (4, 5) = 1$ ）。

$M = 60$ 、 $M_{1} = 20$ 、 $M_{2} = 15$ 、 $M_{3} = 12$ 。

$M_{1^{- 1}} \equiv 20^{- 1} \equiv 2^{- 1} \equiv 2 [PARSE ERROR: Undefined("Command(\"pmod\")")] 3$

$M_{2^{- 1}} \equiv 15^{- 1} \equiv 3^{- 1} \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 4$ （ $3 \cdot 3 = 9 \equiv 1$ ）

$M_{3^{- 1}} \equiv 12^{- 1} \equiv 2^{- 1} \equiv 3 [PARSE ERROR: Undefined("Command(\"pmod\")")] 5$ （ $2 \cdot 3 = 6 \equiv 1$ ）

$x_{0} = 1 \cdot 20 \cdot 2 + 2 \cdot 15 \cdot 3 + 3 \cdot 12 \cdot 3 = 40 + 90 + 108 = 238 \equiv 58 [PARSE ERROR: Undefined("Command(\"pmod\")")] 60$

5.55. CRT の代数的だいすうてき意味いみ

$[PARSE ERROR: Undefined("Command(\"gcd\")")] (m_{i}, m_{j}) = 1$ （ $i \neq j$ ）のとき環かんの同型どうけい

Z / M Z ≅ Z / m_{1} Z \times \dots \times Z / m_{k} Z

が成立せいりつする。これが CRT の代数的だいすうてきな本質ほんしつであり、 $M$ の剰余じょうよ類るいの情報じょうほうが各法かくほうの余あまりの組くみみ合あわせに一対一いちたいいちで対応たいおうすることを意味いみする。

6応用おうよう：調日算ちょうにちざん

「月曜日げつようびから何なん日にち後ごかを求もとめる」などの曜日ようび計算けいさんは $[PARSE ERROR: Undefined("Command(\"bmod\")")] 7$ の計算けいさんである。複数ふくすうの周期しゅうきが絡からむ場合ばあいに CRT が使用しようできる。詳細しょうさいは調日算ちょうにちざんの講義こうぎで扱あつかう。

data/lecture/math/number-theory/calendar-arithmetic.lecture.n.md

7見分みわけ方かた

余あまり条件じょうけんが複数ふくすうあり、法ほうが互たがいに素そ → CRT で一意いちいに解とける
法ほうが互たがいに素そでない場合ばあい → まず互たがいに素そな部分ぶぶんに分解ぶんかいするか、一般いっぱん化か CRT を使用しようする
$M$ の剰余じょうよ環かんの計算けいさん → CRT で小ちいさな法ほうに分解ぶんかいして並列計算へいれつけいさんする

8どこまで成立せいりつするか

法ほうが互たがいに素そでない場合ばあいは解かいの存在そんざい条件じょうけんが変かわる（ $a_{1} \equiv a_{2} [PARSE ERROR: Undefined("Command(\"pmod\")")] [PARSE ERROR: Undefined("Command(\"gcd\")")] (m_{1}, m_{2})$ が必要ひつよう）。存在そんざいする場合ばあいの一意性いちいせいは $lcm (m_{1}, m_{2})$ を法ほうとした意味いみに弱よわまる。

9最終形さいしゅうけい

[PARSE ERROR: Undefined("Command(\"boxed\")")] x \equiv \sum_{i = 1}^{k} a_{i} M_{i} M_{i^{- 1}} [PARSE ERROR: Undefined("Command(\"pmod\")")] M, M_{i} = \frac{M}{m_{i}}, M_{i} M_{i^{- 1}} \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] m_{i}

10一言ひとことでいうと

互たがいに素そな法ほうの余あまり条件じょうけんは独立どくりつな情報じょうほうを与あたえ、積せきの法ほうのもとで一意いちいの解かいが構成こうせいできる—中国ちゅうごくの古典こてんから現代げんだいの暗号あんごう理論りろんまで貫つらぬく定理ていり。