中国の剰余定理
中国の剰余定理(ちゅうごくのじょうよていり、Chinese remainder theorem)は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理(ちゅうごくじんのじょうよていり)、孫子の定理(そんしのていり、Sunzi's theorem)とも呼ばれる。
『孫子算経』には、「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という問題とその解法が書かれている。中国の剰余定理は、この問題を他の整数についても適用できるように一般化したものである。
3~5世紀頃成立したといわれている中国の算術書『孫子算経』には、以下のような問題とその解答が書かれている。
今有物、不知其数。三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。問物幾何?
答曰:二十三。
術曰:『三・三数之、剰二』、置一百四十。『五・五数之、剰三』、置六十三。『七・七数之、剰二』、置三十。并之、得二百三十三。以二百一十減之、即得。凡、三・三数之、剰一、則置七十。五・五数之、剰一、則置二十一。七・七数之、剰一、則置十五。一百六以上、以一百五減之、即得。
日本語では、以下のようになる。
今物が有るが、その数はわからない。三つずつにして物を数えると、二余る。五で割ると、三余る。七で割ると、二余る。物はいくつあるか?
答え:二十三。
解法:三で割ると、二余る数として、百四十と置く。五で割ると、三余る数として、六十三と置く。七で割ると、二余る数として、三十と置く。これらを足し合わせて、二百三十三を得る。これから二百十を引いて、答えを得る。一般に、三つずつにして物を数え、一余ると、その度に七十と置く。五で割った余りに二十一をかける。七で割った余りに十五をかける。百六以上ならば、百五を引くことで、答えを得る。
この問題がいつ頃から知られていたかについては定かではない。この問題は、『孫子算経』とともに日本にも伝わり、後に和算の隆盛した江戸時代には、「百五減算」として知られた。
"Chinese remainder theorem"という名前の使用は、少なくともアメリカの数学者レオナード・E・ディクソンによる著書 Introduction to the Theory of Numbers (1929) の中に見られる。
中国の剰余定理の最も基本的な形は次のような形式で述べることができる。
与えられた二つの整数 m, n が互いに素ならば、任意に与えられる整数 a, b に対し、連立合同式
x ≡ a (mod m),
x ≡ b (mod n)
を満たす整数 x が mn を法として一意的に存在する。
(解の存在) 二つの整数 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 個の整数 m1, m2, ..., mk がどの二つも互いに素ならば、任意に与えられる整数 a1, a2, ..., ak に対し
x ≡ a1 (mod m1),
x ≡ a2 (mod m2),
…
x ≡ ak (mod mk)
を満たす整数 x が m1m2…mk を法として一意的に存在する。
数学的帰納法で証明する。
k = 1 のとき、
x = a1
が解となる。k のとき、数学的帰納法の仮定が成立つとすると、
b ≡ a1 (mod m1),
b ≡ a2 (mod m2),
…
b ≡ ak (mod mk)
を満たす整数 b が法 m1m2…mk に関して一意的に存在する。このとき、積 m1m2…mk と mk+1 とが互いに素とすると、補助定理より、
x ≡ b (mod m1m2…mk),
x ≡ ak+1 (mod mk+1)
を満たす整数 x が法 m1m2…mk+1 に関して一意的に存在する。
よって k + 1 のときも命題が成り立つことが示された。Q.E.D.
ガウスは『整数論』(1801年)において、法 m1, m2, …, mk に関して対称な解法を示した。
(解の存在)
整数 m1, m2, ..., mk がどの二つも互いに素ならば、
M = m1m2...mk ,
M = m1M1 = m2M2 = …  = mkMk
と置くと、各 mi と Mi とは互いに素なので、補助定理により、i = 1, 2, …, k に対して、
Miti ≡ 1 (mod mi),
となる ti が存在する。このとき、
x ≡ a1M1t1 + a2M2t2 + … + akMktk (mod M)
は与えられた連立合同式の解になる。
例えば、x の第1項の法 m1 に関する剰余は a1 に合同であり、第2項から第 k 項は M2 から Mk が m1 の倍数となるので、x は法 m1 に関して a1 と合同になる。
i = 2, 3, …, k に関しても同様にして、
x ≡ ai (mod mi)
を満たすことがわかる。
(解の一意性)
y を任意の解とすると、x − y は
x − y ≡ 0 (mod m1),
x − y ≡ 0 (mod m2)
…
x − y ≡ 0 (mod mk)
を満たす。よって、x − y は法 m1, m2, …, mk で割り切れる。m1, m2, …, mk は互いに素なので、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 = 3m1 + 2 (m1 ∈ Z) と表せる。これを2番目の式に代入し、両辺から 2 を引くと、
3m1 ≡ 1 (mod 5).
を得る。この式の両辺に 2 をかけると、(左辺)= 6m1 = 5m1 + m1 ≡ m1 (mod 5) である(これは、 Z/5Z において 2 が 3 の乗法に関する逆元であることに他ならない。)ので、
m1 ≡ 2 (mod 5)
を得る。したがって、m1 = 5m2 + 2 (m2 ∈ Z) と表せ、これにより x = 15m2 + 8 を得る。更にこれを連立合同式の3番目の式に代入すると、
15m2 + 8 ≡ 2 (mod 7)
を得る。この式の両辺から 8 を引き、また 15m2 = 14m2 + m2 ≡ m2 (mod 7) であることに注意すると、
m2 ≡ −6 (mod 7).
更にこれは、−6 ≡ 1 (mod 7) より
m2 ≡ 1 (mod 7)
と書き直せるので、m2 = 7m3 + 1 (m3 ∈ Z) と表せ、これにより x = 105m3 + 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 ≡ a1 (mod 3),
x ≡ a2 (mod 5),
x ≡ a3 (mod 7)
x = −35a1 + 21a2 + 15a3
であることが容易に確かめられる。しかも定理により解は 3 × 5 × 7 = 105 を法として一意的であったから、すべての解は k を任意の整数として、
−35a1 + 21a2 + 15a3 + 105k
と表されることもわかる。つまり、これがこの問題の一般解である。
上記の定理は整数とその剰余に関するものであるが、これを一般の単位元を持つ環とそのイデアルに対するものに拡張することができる。すなわち:
R を単位元を持つ環とし、R の両側イデアル I1, I2, ..., Ik がどの二つも互いに素である(すなわち、i ≠ j ならば Ii + Ij = R が成立する)と仮定する。このとき、任意に与えられた a1, a2, ..., ak ∈ R に対して、
\begin{align}
x &\equiv a_1 \pmod{I_1}, \\
x &\equiv a_2 \pmod{I_2}, \\
& \vdots \\
x &\equiv a_k \pmod{I_k}
\end{align}
を満たす x ∈ R が、イデアル \textstyle I = \bigcap_{i=1}^k I_i  を法として一意的に存在する。言い換えると、自然な環準同型
R \to \prod_{i=1}^k R/I_i, \; x \mapsto (x + I_1, x + I_2, \dotsc , x + I_k)
は全射であり、準同型定理より環同型
R/I \cong \prod_{i=1}^k R/I_i
が得られる。これも中国の剰余定理と呼ばれる。さらに R が可換環であるとき、
I_1 I_2 \dotsm I_k \supset \bigcap_{i=1}^k I_i
が二つの異なるイデアルが互いに素であることから従う。逆向きの包含は一般に成立するので、
I_1 I_2 \dotsm I_k = \bigcap_{i=1}^k I_i
が成立する。(R が可換でないときは、「互いに素」という条件を仮定しても上記の等号は一般には成立しない。)
整数 m, n を(通常の意味で)互いに素であるとする。拡張されたユークリッドの互除法から mZ + nZ = Z, すなわちイデアルの意味で互いに素であることがわかり、また逆も成立する。従って、 Z/mnZ は Z/mZ × Z/nZ に同型である。
R を単項イデアル整域とする。u1, u2, ..., uk ∈ R がどの二つも互いに素であるとき、u = u1u2…uk とすると、R/uR は R/u1R × R/u2R × … × R/ukR に同型である。
k を代数的閉体とする。多項式 f(x) ∈ k[x] の相異なる l 個の根を ai, 重複度を ni とすると、
k[x]/(f(x)) \cong \prod_{i=1}^l k[x]/\big((x-a_i)^{n_i}\big)
が成り立つ。