中国剰余定理 【大学受験の内容から大学の環論へ】

2022年9月15日

中国剰余定理 (Chinese Remainder Theorem) は整数の分野で有名です。

難しい受験問題で連立合同式に関連したり、大学数学では可換環論の入門において学習します。

厳密証明については、大学レベルの内容は複雑になるので、なるべく算数的に理解できる内容を例にして、解説を始めています。

定理の証明も書いていますが、難し過ぎる部分は証明を後にまわしています。

定理は、連立合同式の解が存在するということを主張しているもので、具体的な解の求め方は定理の主張には現れていないので注意です。

具体的な解の求め方は、定理の証明の考え方に現れています。ただ、シンプルな内容なので、算数的な見方で、親しめるかと思います。

いきなり一般的な定理を述べると複雑なので、まずは具体的な整数を用いた形で中国剰余定理の内容を書いておきます。

中国剰余定理 :例を通して使ってみる

【具体例】

3 と 5 という最大公約数が 1 である自然数について、
3 で割ると 2 余り、5 で割ると 3 余る整数が 0 以上 14 以下の範囲内にただ 1 つ存在します。

※ 二つの整数の最大公約数が 1 のときに互いに素ともいいます。

はじめに、3 と 5 という最大公約数が 1 となっている自然数（ 1 以上の整数）が与えられています。

まず、(3 × 5 – 1) 以下、つまり 14 以下で 0 以上の範囲内の整数を意識します。

0 以上 14 以下の範囲内にただ 1 つ存在とありますが、与えられた最大公約数が 1 となっている二つの自然数によって、考える範囲が異なります。二つの整数を掛け合わせた値から 1 を引き、範囲の限界とします。

3 で割ると 2 余り、5 で割ると 3 余る整数が本当に範囲内にただ 1 つだけあるのかということを確認してみます。

該当の整数を求める手順

0 以上 14 以下の範囲内にある 15 個の整数について、「5 で割ると 3 余る整数」を拾い出します。そして、それらの中で、「3 で割ると 2 余る整数」が該当する整数です。

表計算ソフトで絞り込むフィルターの発想です。

3, 8, 13 が 0 以上 14 以内の範囲にある「5 で割ると 3 余る整数たち」です。この 3 個の整数と異なる 0 以上 14 以内の整数は、5 で割ったときの余りの条件を満たさないので、論外な数として除外します。

こういうわけで、3, 8, 13 について、3 で割ったときの余りを調べてみます。

3 = 3 × 1 + 0,
8 = 3 × 2 + 2,
13 = 3 × 4 + 1

8 を 3 で割った余りが 2 で条件に該当します。

0 以上 14 以下の範囲にある 15 個すべてについて、「3 で割ると 2 余り、5 で割ると 3 余る」かどうかを確認しました。確かに 8 ただ 1 つのみが該当しました。

この該当する整数へ辿り着くまでの手順は、実は中国剰余定理の証明の手順そのものを具体的に述べたものになります。整数がもつ性質を利用して、手順をつくっています。

それでは、割る数が 3 つあるときの求め方を述べておきます。

割る数が3つのとき

3 と 5 と 7 は、どの二つも最大公約数が 1 です。

3 で割ると 2 余り,
5 で割ると 3 余り,
7 で割ると 4 余る、

この三つの条件を満たす整数が 0 以上 104 以下の範囲内に、ただ 1 つだけ存在します。

割る数 7 が増えて、割る数が三つになりました。しかし、求め方は、先ほどと同じ要領です。

0 以上 104 以下である 105 個の整数の中から、7 で割ると余りが 4 となる整数を拾い上げます。

4 = 7 × 0 + 4,
11 = 7 × 1 + 4,
　　…
102 = 7 × 14 + 4

7 で割ると余りが 4 となる整数は、これら 15 個です。これは偶然なのか、15 個の 15 は 3 × 5 と他の割る数の積となっています。

拾い上げたこれら 15 個の整数をすべて書き出しておきます。4, 11, 18, 25, 32, 39, 46, 53, 60, 67, 74, 81, 88, 95, 102 です。

これらの中で、5 で割ると余りが 3 となるものは、

18 = 5 × 3 + 3,
53 = 5 × 10 + 3,
88 = 5 × 17 + 3

最後の割る数は 3 です。奇遇なことに、3 個の整数が残りました。「7 で割ると 4 余る、5 で割ると 3 余る」という条件で絞りました。

残りの 102 個の整数は条件に合わないので除外です。

この中で 3 で割ったときに余りが 2 になるものが存在するのかどうかを確かめます。

18 = 3 × 6 + 0,
53 = 3 × 17 + 2,
88 = 3 × 29 + 1 です。

これで、0 以上 104 以下の整数の中で、53 のみが該当する整数ということになります。やはり、ただ 1 つしかありませんでした。

割る数が 3 つや 4 つになっても、同じ要領で絞っていくと該当の整数へ辿り着きます。

ここから、連立合同式の解が存在することについて考えます。

中国剰余定理 :なぜ解が存在したのかを考える

3 で割ると 2 余り、5 で割ると 3 余る整数が 0 以上 14 以下の範囲内にただ 1 つ存在した必然性を追求します。そこで、余りについての範囲というものを正しく認識しておくことが大切になります。

5 で割ったときの余りは、
0, 1, 2, 3, 4 の 5 個

一般に、自然数 k で割ったときの余りは、0, 1, … , k – 2, k – 1 の k 個です。k = 3 だと、0, 1, 2 の 3 個になります。

5 で割るときに考えられる余りは 5 通りなので、1 つの周期の長さは 5 個の余りによって形成されていることが分かります。

ここで、周期といっているのは、割られる数を 5 大きくしても余りが変わらないという性質を考えているからです。

7 を 5 で割ると余りが 2 です。割られる数 7 を 5 大きくした 12 を 5 で割ると余りが 2 です。

さらに 5 を増やしても、
17 を 5 で割った余りは 2 です。

余りの周期に注目して範囲を分割

0, 1, 2, 3, 4
　↓ + 5
5, 6, 7, 8, 9
　↓ + 5
10, 11, 12, 13, 14

※ 4, 9, 14 は、どれも 5 で割ったときの余りが 4 です。縦に見たときに、どれも同じになるように並べています。

5 で割った余りは 5 通りあったので、周期的に現れる 5 の余りたちを 5 個のセットでくくっておきます。0 以上 14 以下の整数たちを整理して分けることができました。

{0, 1, 2, 3, 4},
{5, 6, 7, 8, 9},
{10, 11, 12, 13, 14} というセットには、どれにも 5 で割ったときの 5 通りの余りが現れています。

ちょうど 3 つのセットに分けられたのですが、これは計算のうちです。

0 以上 14 以下の 15 個は 5 × 3 だからです。1 つのセットが 5 個の整数で形成されているので、ちょうど 3 セット現れるというわけです。

5 で割ったときに余りが 3 となる 3, 8, 13 を取り出しました。実は、それぞれのセットに含まれている 5 で割ったときに余りが 3 となるものを取り出していたのです。

★ {0, 1, 2, 3, 4} から 3
★ {5, 6, 7, 8, 9} から 8
★ {10. 11, 12, 13, 14} から 13

このようにして、0 以上 14 以下の範囲内の整数から 5 で割ったときの余りが 3 となるものを抽出しました。「3, 8, 13」と 3 個の整数を抽出するように計算しています。

どうして 3 個抽出したのかというと、3 で割ったときに現れる余りが 3 通りあるからです。

抽出した 3 と 8 と 13 のそれぞれを 3 で割った余りを計算すると、0, 2, 1 です。

これは偶然かというと、実は次の考えからです。

3 = 5 × 0 + 3,
8 = 5 × 1 + 3,
13 = 5 × 2 + 3 です。

この検算（除法の定理）の形の余りは、5 で割った余りが 3 ということで、余り部分はすべて 3 です。

そして、商の部分は 0, 1, 2 と 0 以上 (3 – 1) 以下の整数がすべて 1 つずつ現れています。

5 と 3 の最大公約数が 1 なので、
5 × 0, 5 × 1, 5 × 2 を 3 で割ったときの余りはすべて異なります。
※ 実はこの部分に初等整数論の定理を使っています。

ここから、中国剰余定理を証明するために必要な準備をします。

よく使う初等整数論の定理

先ほどの証明で、5 × 1 を 3 で割ったときの余りと 5 × 2 を 3 で割ったときの余りが、3 と 5 の最大公約数が 1 なので、異なるということを述べました。

この内容に使われている定理を紹介します。
次の【定理 1】の対偶を使っています。

【定理 1】
a を 0 ではない整数で、自然数 m との最大公約数が 1 とします。
このとき、整数 x と y について、
「ax を m で割った余りと ay を m で割った余りが等しい」ならば、
「x を m で割った余りと y を m で割った余りが等しい」です。

ユークリッド整域より

※ この定理の証明は、リンク先の記事の最後の方で解説しています。

対偶も正しいということで、次を得ます。

5 × 1 を 3 で割った余りと、5 × 2 を 3 で割った余りが等しくないことを保証するのが、この【定理 1 の対偶】です。a として 5、m として 3 を考えます。

x = 1, y = 2 としています。

x = 1 を 3 で割った余りと y = 2 を 3 で割った余りは等しくないです。5 と 3 の最大公約数は 1 なので、【定理 1 の対偶】から、5 × x を 3 で割った余りと 5 × y を 3 で割った余りは等しくありません。

つまり、5 × 1 と 5 × 2 は、3 で割ったときの余りが等しくないということが、計算をしなくても分かります。計算しなくても分かるということは、文字を使った一般的な証明のときに有効です。

ここから、割る数が二つのときの証明を書いておきます。

中国剰余定理 :割る数が二つのときの証明

割る数が二つのときの証明を書いておきます。割る数が三つ以上の有限個数のときについては、大学の数学科で環論入門の講義などで扱われます。

証明で使う余りについての定理を書いておきます。

【定理 2 】

n を自然数とし、x と y と r を整数とする。

このとき、x を n で割ったときの余りと、y を n で割ったときの余りが異なるならば、x + r を n で割ったときの余りと y + r を n で割ったときの余りは異なる。

この【定理 2】と【定理 1 の対偶】を中国剰余定理の証明で使います。

※これらの証明については、余り-整数問題というブログ記事の【命題 2】と【命題 4】で証明を解説しています。

抽象的な定理の証明

【命題】

m と n を 2 以上の自然数とする。また、整数 r と t を、それぞれ m 以下、n 以下の非負整数とする。

このとき、m で割ると余りが r で、n で割ると余りが t となる整数 k が、(mn－1) 以下の範囲にただ 1 つのみ存在する。

＜証明＞

m で割ったときの余りが r となる 0 以上 (mn – 1) 以下の範囲にある整数は、

r + 0, r + m, r + 2m, … , r + (n – 1)m の n 個です。

0, 1, 2, … , (n – 1) の n 個の整数は、n で割ったときの余りがすべて異なります。そして、m と n の最大公約数が 1 ということから、【定理 1 の対偶】が使えます。

よって、0, m, 2m, … , (n – 1)m のそれぞれについて、n で割った余りは、どの二つも相異なります。

よって、n で割ったときに現れる可能性のある余りは、すべてこの中に含まれています。
※ n で割ったときの余りは、0 以上 (n – 1) 以下の n 個だからです。

よって、0, m, 2m, … , (n – 1)m たちに一律に r を加えた整数たちをすべて集めます。

【定理 2】より、
r + 0, r + m, r + 2m, … , r + (n – 1)m を n で割ったときの余りはすべて異なり、余りが 0 から (n – 1) までのすべて現れるということになります。

この中で、余りが t となっているものを r + im とすると、これが求める整数 k です。ただ 1 つのみが存在するというのは、n で割ったときの余りがすべて異なるからです。【証明完了】

＜注意＞

自然数 n で割ったときの余りは、
0 以上 n – 1 以下の n 種類の非負整数となります。

そのため、部屋割り論法を使うチャンスになります。

n + 1 個の非負整数が n で割ったときの余りであるときに、n 種類しか余りがないため、少なくとも 2 つの余りは重複することになります。

この手の内容が受験問題で出題されるときもあるので、具体的な数で余りの種類が何種類あるのかということを意識しておくと良いかと思います。

最後に、大学で扱う可換環論の内容です。

中国剰余定理 :可換環論から観察

記号ですが、大学の環論入門で扱われる内容の記号を紹介します。

3 で割ったときに 2 余る整数たちを総じて 2 + 3Z と表します。

3 で割った余りは 3 通りあるので、
0 + 3Z, 1 + 3Z, 2 + 3Z と表します。

この 3 つを集めたものを Z/3Z と表します。

i + 3Z ですが、i が 3 以上の整数のときは、次のように調整をして、0 か 1 か 2 になるようにします。

i を 3 で割ったときの余り r を求めて、
i + 3Z = r + 3Z とするということです。

例えば、i = 5 のときに、5 を 3 で割った余りが 2 ですから、
5 + 3Z = 2 + 3Z と調整をします。

このようにして、5 で割った余りは 0 以上 4 以下の整数ですから、
0 + 5Z, 1 + 5Z, … , 4 + 5Z を集めたものを Z/5Z とします。

7 で割った余りについても、Z/7Z を考えます。

0 + 7Z から 6 + 7Z という 7 通りを集めたものです。

これら 3 種類の集まりたちについて、
Z/3Z × Z/5Z × Z/7Z と直積をとります。

3 で割ると 2 余り、5 で割ると 3 余り、7 で割ると 4 余るということは、
直積集合において、
(2 + 3Z, 3 + 5Z, 4 + 7Z) という要素です。

この条件に該当する 0 以上 104 以下の整数というものは、大学の記号を使うと Z/105Z です。

この 105 で割った余りですから、0 以上 104 以下ということです。

そして、この 105 は 3 × 5 × 7 です。

実は、大学の環論入門で必ずといっていいほど扱われる定理があります。

全単射である環準同型写像、つまり環同型写像が存在するという定理です。しかも、その写像の対応は明確に定められています。

105 で割った余りですから、0 以上 104 以下の整数 x について、上の図のように、
x + 3Z, x + 5Z, x + 7Z という三つ組を対応させると、全単射である環準同型写像となるという定理です。

直積の方は、3 通り × 5 通り × 7 通りなので、105 通りの要素があるわけです。

その中に、(2 + 3Z, 3 + 5Z, 4 + 7Z) があります。

ちょうど、Z/105Z も 105 個の要素があります。

全単射ですから、図のように対応する要素が Z/105Z の中にただ 1 つ存在します。
その対応する要素を x + 105Z とすると、
f(x + 5Z)
= (x + 3Z, x + 5Z, x + 7Z)
= (2 + 3Z, 3 + 5Z, 4 + 7Z)

このブログのはじめに、算数を使って具体的に計算をしました。それは、この x を明らかにするということです。i + 7Z だと、i が 7 以上の整数のときは、i を 7 で割った余りに書き換えるということをします。

そのため、0 以上 104 以下の整数 x を 7 で割ったときに 4 になる可能性を全て考えました。

7 × 14 + 4 = 102 ですから、
x = 4, 11, … , 102 が起こり得る可能性です。

さらに、x + 5Z が 3 + 5Z ですから、x を 5 で割ったときの余りが 3 になるものでなければなりません。そこで、さらに絞られるわけです。

18, 53, 88 が x の可能性です。

さらに、x + 3Z が 2 + 3Z なので、x を 3 で割ったときの余りが 2 となるものが、x に該当します。18, 53, 88 の中で、3 で割ったときの余りが 2 となるものは、 53 だけです。

環論のこの定理まで理解をしていると、対応関係で考察ができます。

f(53 + 105Z)
= (53 + 3Z, 53 + 5Z, 53 + 7Z)
= (2 + 3Z, 3 + 5Z, 4 + 7Z)

53 が、「3 で割ると 2 余り、5 で割ると 3 余り、7 で割ると 4 余る」という条件に該当する範囲内のただ 1 つの整数ということです。

互いに素なイデアル

可換環 R の二つのイデアル I, J について、I + J が 1 を含むときに、I と J を互いに素なイデアルといいます。

I + J もイデアルなので、I + J = R ということです。互いに素なイデアルについて、次の定理が成立します。

【定理 3】

I₁, I₂, … , I_n を可換環 R の互いに素なイデアルとすると、
∩_k I_k = I₁I₂・・・I_n である。

＜証明＞

イデアルの個数 n についての帰納法で示します。

【n = 2 の場合】

I₁I₂ ⊂ I₁ ∩ I₂ は常に成立します。

I₁ + I₂ = R より、a₁ ∈ I₁, a₂ ∈ I₂ が存在して、
1 = a₁ + a₂ と表せます。

任意の x ∈ I₁ ∩ I₂ に対して、
x = xa₁ + xa₂ で、xa₁ , xa₂ ∈ I₁I₂ なので、
x ∈ I₁I₂ です。

よって、I₁ ∩ I₂ = I₁I₂ が成立しています。

次に、n = k のとき定理が成立しているとして、
n = k + 1 のときにも定理が成立することを示します。

【n ≧ 2 の場合】

2 以上 k + 1 以下の自然数 i について、
I₁ と I_i は互いに素だから、
ある x_(i) ∈ I₁ と x_i ∈ I_i が存在して、
1 = x_(i) + x_i と表すことができます。

これらを辺々掛け合わせ、1 = Π_i (x_(i) + x_i)

この右辺を展開したとき、
x₁x₂・・・x_k+1 以外の項には、I₁ の元が少なくとも 1 つが乗じられています。

I₁ の元に R の元を乗じると I₁ の元となるので、
Π_i (x_(i) + x_i) ∈ I₁ + I₂I₃・・・I_k+1

よって、I₁ と I₂I₃・・・I_k+1 は互いに素なイデアルなので、
先ほど示した n = 2 の場合より、
I₁I₂I₃・・・I_k+1
= I₁ ∩ (I₂I₃・・・I_k+1)

帰納法の仮定から、
I₂I₃・・・I_k+1 = ∩_jI_j なので、
I₁I₂I₃・・・I_k+1
= I₁ ∩ (∩_jI_j) = ∩_iI_i【証明完了】

では、この【定理 3】から、大学数学版の中国剰余定理を証明します。

次の定理の I1 から In は、先ほどと同じく、どの二つも互いに素なイデアルという設定です。

中国剰余定理の大学版

f の定め方から、f は環準同型写像であり、
ker f = I₁ ∩ I₂ となっています。

よって、f が全射であることを示せば、n = 2 のときに中国剰余定理が成立していることを示せます。

I₁ と I₂ が互いに素であることから、
ある a ∈ I₁, b ∈ I₂ が存在して、
1 = a + b と表すことができます。

x, y を任意の R の元とすると、xa + yb ∈ R なので、ある z ∈ R を用いて、
z = ya + xb となります。

ここで、
z + I₁ = (ya + xb) + I₁ = xb + I₁ であり、
b = 1 – a だから、
z + I₁ = x(1 – a) + I₁= x + I₁

z + I₂ = (ya + xb) + I₂ = ya + I₂ であり、
a = 1 – b だから、
z + I₂ = y(1 – b) + I₂= y + I₂

つまり、
f(z) = (z + I₁, z + I₂) = (x + I₁, y + I₂)

よって、f が全射であるので、準同型定理から、
R/(I₁ ∩ I₂) と R/I₁ × R/I₂ は同型です。

【n ≧ 2 の場合】

n = k のときに中国剰余定理が成立していると仮定し、n = k + 1 のときにも成立することを示します。

【定理 3】の証明で示したことから、
I₁ と I₂・・・I_k+1 = ∩_jI_j は互いに素です。

I₁ ∩ (∩_jI_j) = ∩_iI_i であり、n = 2 のときに示したことから、
R/∩_iI_i と R/I₁ × R/∩_jI_j は同型です。

帰納法の仮定から、
R/∩_jI_j は R/I₂ ×・・・× R/I_k+1 と同型なので、
R/∩_iI_i は R/I₁ × R/I₂ ×・・・× R/I_k+1 と同型となります。【証明完了】

大学版の中国剰余定理を証明しました。剰余環に慣れる必要がありますが、中国剰余定理を通して、剰余環を練習するのも良いかと思います。

イデアルの積という環論についての基礎的な命題についての記事も投稿しています。

これで今回のブログ記事を終了します。

それでは、読んで頂き、ありがとうございました。