中国の剰余定理

ファイル:Disqvisitiones-800.jpg

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

中国の剰余定理（ちゅうごくのじょうよていり、英: 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 (mod mn)

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

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

x − y ≡ 0 (mod m),

x − y ≡ 0 (mod n)

を満たす。よって、x − y は法 m および法 n で割り切れる。m と n とは互いに素なので、x − y は 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 を法として一意的に存在する。

一般的な定理の証明

数学的帰納法で証明する。 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 に関して対称な解法を示した。

（解の存在） 整数 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 に対して、

[math]\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}[/math]

を満たす x ∈ R が、イデアル [math]\textstyle I = \bigcap_{i=1}^k I_i [/math] を法として一意的に存在する。言い換えると、自然な環準同型

[math]R \to \prod_{i=1}^k R/I_i, \; x \mapsto (x + I_1, x + I_2, \dotsc , x + I_k)[/math]

は全射であり、準同型定理より環同型

[math]R/I \cong \prod_{i=1}^k R/I_i[/math]

が得られる。これも中国の剰余定理と呼ばれる。さらに R が可換環であるとき、

[math]I_1 I_2 \dotsm I_k \supset \bigcap_{i=1}^k I_i [/math]

が二つの異なるイデアルが互いに素であることから従う。逆向きの包含は一般に成立するので、

[math]I_1 I_2 \dotsm I_k = \bigcap_{i=1}^k I_i [/math]

が成立する。（R が可換でないときは、「互いに素」という条件を仮定しても上記の等号は一般には成立しない。）

系

• 整数 m, n を（通常の意味で）互いに素であるとする。拡張されたユークリッドの互除法から mZ + nZ = Z, すなわちイデアルの意味で互いに素であることがわかり、また逆も成立する。従って、 Z/mnZ は Z/mZ × Z/nZ に同型である。
• R を単項イデアル整域とする。u₁, u₂, ..., u_k ∈ R がどの二つも互いに素であるとき、u = u₁u₂…u_k とすると、R/uR は R/u₁R × R/u₂R × … × R/u_kR に同型である。
• k を代数的閉体とする。多項式 f(x) ∈ k[x] の相異なる l 個の根を a_i, 重複度を n_i とすると、

[math]k[x]/(f(x)) \cong \prod_{i=1}^l k[x]/\big((x-a_i)^{n_i}\big)[/math]

が成り立つ。

関連文献

• ガウス 『ガウス整数論』 高瀬正仁 訳、朝倉書店〈数学史叢書〉、1995-06-20（原著1801年）。ISBN 4-254-11457-5。 - ラテン語原典からの日本語訳。
• 高木貞治 『初等整数論講義』 共立出版、1971-10-15、第2版。ISBN 4-320-01001-9。
• Hardy, G. H.; Wright, E. M. (31 July 2008), Heath-Brown, Roger; Silverman, Joseph; Wiles, Andrew, eds., An Introduction to the Theory of Numbers (sixth ed.), USA: Oxford University Press, ISBN 978-0-19-921986-5, http://ukcatalogue.oup.com/product/9780199219865.do#.UdgOFeaCjIU 
  • G・H・ハーディ・E・M・ライト 『数論入門I』 示野信一・矢神毅 訳、シュプリンガー・フェアラーク東京〈シュプリンガー数学クラシックス8〉、2001年7月。ISBN 978-4-431-70848-3。 - 原書第5版（1979年）の邦訳。
  • G・H・ハーディ・E・M・ライト 『数論入門I』 示野信一・矢神毅 訳、丸善出版〈シュプリンガー数学クラシックス8〉、2012年7月。ISBN 978-4-621-06226-5。 - ハーディ & ライト (2001)の再出版。
• 前原昭二 『数学基礎論入門』 朝倉書店〈復刊基礎数学シリーズ23〉、2006-03-20（原著1977-06-01）。ISBN 978-4-254-11723-3。

関連項目

• 百五減算
• プリューファー整域
• ベズーの等式
• Disquisitiones Arithmeticae - 『ガウス整数論』
• RSA暗号

外部リンク

• 孫子算経（原文） (UTF-8)
• 中国の剰余定理
• 中国の剰余定理　解説 (PDF)
• 鬼谷算（きこくさん）
• Weisstein, Eric W. “Chinese Remainder Theorem”. MathWorld（英語）.