中国の剰余定理とは？わかりやすく解説

ガウスは『整数論』（1801年）において中国の剰余定理を明確に記述して証明した^[1]。

中国の剰余定理（ちゅうごくのじょうよていり、英: Chinese remainder theorem）は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理（ちゅうごくじんのじょうよていり）、孫子の定理（そんしのていり、英: Sunzi's theorem）とも呼ばれる。

『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。

背景

3 - 5世紀頃成立したといわれている中国の算術書『孫子算経』には、以下のような問題とその解答が書かれている^[2]。

今有物、不知其数。三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。問物幾何？
答曰：二十三。
術曰：『三・三数之、剰二』、置一百四十。『五・五数之、剰三』、置六十三。『七・七数之、剰二』、置三十。并之、得二百三十三。以二百一十減之、即得。凡、三・三数之、剰一、則置七十。五・五数之、剰一、則置二十一。七・七数之、剰一、則置十五。一百六以上、以一百五減之、即得。

日本語では、以下のようになる。

今物が有るが、その数はわからない。三つずつにして物を数えると^[3]、二余る。五で割ると、三余る。七で割ると、二余る。物はいくつあるか？
答え：二十三。
解法：三で割ると、二余る数として、百四十と置く。五で割ると、三余る数として、六十三と置く。七で割ると、二余る数として、三十と置く。これらを足し合わせて、二百三十三を得る。これから二百十を引いて、答えを得る。一般に、三つずつにして物を数え、一余ると、その度に七十と置く^[4]。五で割った余りに二十一をかける。七で割った余りに十五をかける。百六以上ならば、百五を引くことで、答えを得る。

この問題がいつ頃から知られていたかについては定かではない。この問題は、『孫子算経』とともに日本にも伝わり、後に和算の隆盛した江戸時代には、「百五減算」として知られた。

13世紀、南宋末の数学家秦九韶は、一次合同式をユークリッドの互除法と同等の方法で解くことで、中国の剰余定理と同等の結果を得ていた。このことは、宣教師によって19世紀のヨーロッパにも伝えられ、ガウスの方法と同等のものであることが確かめられた。^[要出典]

"Chinese remainder theorem"という名前の使用は、少なくともアメリカの数学者レオナード・E・ディクソンによる著書 Introduction to the Theory of Numbers (1929) の中に見られる^[5]。

定理

中国の剰余定理の最も基本的な形は次のような形式で述べることができる。

補助定理

与えられた二つの整数 m, n が互いに素ならば、任意に与えられる整数 a, b に対し、連立合同式

x ≡ a (mod m),

x ≡ b (mod n)

を満たす整数 x が mn を法として一意的に存在する^[6]。

補助定理の証明

（解の存在）二つの整数 m, n が互いに素ならば、ユークリッドの互除法により適当な整数 u, v が存在して、

mu + nv = 1

となるようにできる。このとき、

mu ≡ 1 (mod n),

nv ≡ 1 (mod m)

が成り立つので、

x = anv + bmu

とおくと、

x = a(1 − mu) + bmu = a + (b − a) mu ≡ a (mod m)

また、

x = anv + b(1 − nv) = b + (a − b) nv ≡ b (mod n)

x は与えられた連立合同式の解となる。

（解の一意性） y を任意の解とすると、x − y は

x − y ≡ 0 (mod m),

x − y ≡ 0 (mod n)

を満たす。よって、x − y は m と n との公倍数であるが、m と n とは互いに素なので、それらの最小公倍数 mn の倍数となり、

x − y ≡ 0 (mod mn)

すなわち、x と y とは法 mn に関して合同になる。 Q.E.D.

一般的な定理

これは明らかに次のように拡張できる。すなわち：

与えられた k 個の整数 m₁, m₂, ..., m_k がどの二つも互いに素ならば、任意に与えられる整数 a₁, a₂, ..., a_k に対し

x ≡ a₁ (mod m₁),

x ≡ a₂ (mod m₂),

…

x ≡ a_k (mod m_k)

を満たす整数 x が m₁m₂…m_k を法として一意的に存在する。

一般的な定理の証明

数学的帰納法で証明する^[7]。 k = 1 のとき、

x = a₁

が解となる。k のとき、数学的帰納法の仮定が成立つとすると、

b ≡ a₁ (mod m₁),

b ≡ a₂ (mod m₂),

…

b ≡ a_k (mod m_k)

を満たす整数 b が法 m₁m₂…m_k に関して一意的に存在する。このとき、積 m₁m₂…m_k と m_k+1 とが互いに素とすると、補助定理より、

x ≡ b (mod m₁m₂…m_k),

x ≡ a_k+1 (mod m_k+1)

を満たす整数 x が法 m₁m₂…m_k+1 に関して一意的に存在する。よって k + 1 のときも命題が成り立つことが示された。Q.E.D.

ガウスの証明

ガウスは『整数論』（1801年）において、法 m₁, m₂, …, m_k に関して対称な解法を示した^[8]^[9]。

（解の存在）整数 m₁, m₂, ..., m_k がどの二つも互いに素ならば、

M = m₁m₂...m_k ,

M = m₁M₁ = m₂M₂ = … = m_kM_k

と置くと、各 m_i と M_i とは互いに素なので、補助定理により、i = 1, 2, …, k に対して、

M_it_i ≡ 1 (mod m_i),

となる t_i が存在する。このとき、

x ≡ a₁M₁t₁ + a₂M₂t₂ + … + a_kM_kt_k (mod M)

は与えられた連立合同式の解になる。例えば、x の第1項の法 m₁ に関する剰余は a₁ に合同であり、第2項から第 k 項は M₂ から M_k が m₁ の倍数となるので、x は法 m₁ に関して a₁ と合同になる。 i = 2, 3, …, k に関しても同様にして、

x ≡ a_i (mod m_i)

を満たすことがわかる。

（解の一意性） y を任意の解とすると、x − y は

x − y ≡ 0 (mod m₁),

x − y ≡ 0 (mod m₂)

…

x − y ≡ 0 (mod m_k)

を満たす。よって、x − y は法 m₁, m₂, …, m_k で割り切れる。m₁, m₂, …, m_k は互いに素なので、x − y は法の最小公倍数 M で割り切れる。

x − y ≡ 0 (mod M)

すなわち、x と y とは法 M に関して合同になる。Q.E.D.

計算法

定理により解が存在することは保証されているが、実際に解を計算できるかどうかとは別問題である。ただし、中国の剰余定理の場合は解を計算することも容易であり、その方法も幾つかある。

直接計算による方法

前述の『孫子算経』の問題を考える。すなわち、連立合同式

x ≡ 2 (mod 3),

x ≡ 3 (mod 5),

x ≡ 2 (mod 7)

を同時に満たす整数 x を求める。まず、1番目の式より x = 3m₁ + 2 (m₁ ∈ Z) と表せる。これを2番目の式に代入し、両辺から 2 を引くと、

3m₁ ≡ 1 (mod 5).

を得る。この式の両辺に 2 をかけると、（左辺）= 6m₁ = 5m₁ + m₁ ≡ m₁ (mod 5) である（これは、 Z/5Z において 2 が 3 の乗法に関する逆元であることに他ならない。）ので、

m₁ ≡ 2 (mod 5)

を得る。したがって、m₁ = 5m₂ + 2 (m₂ ∈ Z) と表せ、これにより x = 15m₂ + 8 を得る。更にこれを連立合同式の3番目の式に代入すると、

15m₂ + 8 ≡ 2 (mod 7)

を得る。この式の両辺から 8 を引き、また 15m₂ = 14m₂ + m₂ ≡ m₂ (mod 7) であることに注意すると、

m₂ ≡ −6 (mod 7).

更にこれは、−6 ≡ 1 (mod 7) より

m₂ ≡ 1 (mod 7)

と書き直せるので、m₂ = 7m₃ + 1 (m₃ ∈ Z) と表せ、これにより x = 105m₃ + 23 を得る。すなわち、

x ≡ 23 (mod 105)

が求める解である。この方法は、計算が煩雑なものになるという欠点がある一方、連立合同式の法が互いに素とならない状況、すなわち中国の剰余定理が適用できない場合においても利用できる。

ユークリッドの互除法

引き続き『孫子算経』の問題を考える。3 と 5 × 7 = 35, 5 と 3 × 7 = 21, 7 と 3 × 5 = 15 はそれぞれ互いに素であるから、拡張されたユークリッドの互除法により、 (m, n) = (3, 35), (5, 21), (7, 15) それぞれについて、不定方程式

mx + ny = 1

の整数解（特殊解）が計算できる。具体的には、

3 × 12 + 35 × (−1) = 1,

5 × (−4) + 21 × 1 = 1,

7 × (−2) + 15 × 1 = 1

となる。したがって、以下の合同式が成立する：

－35 ≡ 1 (mod 3),

21 ≡ 1 (mod 5),

15 ≡ 1 (mod 7).

すると、連立合同式

x ≡ a₁ (mod 3),

x ≡ a₂ (mod 5),

x ≡ a₃ (mod 7)

の一つの解が

x = −35a₁ + 21a₂ + 15a₃

であることが容易に確かめられる。しかも定理により解は 3 × 5 × 7 = 105 を法として一意的であったから、すべての解は k を任意の整数として、

−35a₁ + 21a₂ + 15a₃ + 105k

と表されることもわかる。つまり、これがこの問題の一般解である。

定理の一般化

上記の定理は整数とその剰余に関するものであるが、これを一般の単位元を持つ環とそのイデアルに対するものに拡張することができる。すなわち：

R を単位元を持つ環とし、R の両側イデアル I₁, I₂, ..., I_k がどの二つも互いに素である（すなわち、i ≠ j ならば I_i + I_j = R が成立する）と仮定する。このとき、任意に与えられた a₁, a₂, ..., a_k ∈ R に対して、

{\begin{aligned}x&\equiv a_{1}{\pmod {I_{1}}},\\x&\equiv a_{2}{\pmod {I_{2}}},\\&\vdots \\x&\equiv a_{k}{\pmod {I_{k}}}\end{aligned}}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

中国の剰余定理とは？ わかりやすく解説