中国の剰余定理

中国の剰余定理（ちゅうごくのじょうよていり、テンプレート:Lang-en-short）は、中国の算術書『孫子算経』に由来する整数の剰余に関する定理である。あるいは、それを一般化した可換環論における定理でもある。中国人の剰余定理（ちゅうごくじんのじょうよていり）、孫子の定理（そんしのていり）とも呼ばれる。

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

背景

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

今有物、不知其数。三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。問物幾何？

答曰：二十三。

術曰：『三・三数之、剰二』、置一百四十。『五・五数之、剰三』、置六十三。『七・七数之、剰二』、置三十。并之、得二百三十三。以二百一十減之、即得。凡、三・三数之、剰一、則置七十。五・五数之、剰一、則置二十一。七・七数之、剰一、則置十五。一百六以上、以一百五減之、即得。

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

今物が有るが、その数はわからない。三つずつにして物を数えると、二余る。五で割ると、三余る。七で割ると、二余る。物はいくつあるか？

答え：二十三。

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

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

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

"Chinese remainder theorem"という定理の名前は、アメリカの数学者レオナード・E・ディクソンが、数論の歴史についての著書の中で初めて使ったものとされる。

定理

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

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

<math>x \equiv a \pmod m,</math>

<math>x \equiv b \pmod n</math>

を満たす整数 x が mn を法として一意的に存在する。ここで、『mn を法として一意的に存在する』とは次のような意味である。つまり、ある整数 y があって、この y も上の連立合同式の解であるならば、すなわち、

<math>y \equiv a \pmod m,</math>

<math>y \equiv b \pmod n</math>

となるならば、必ず

<math> x \equiv y \pmod{mn}</math>

が成立する。

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

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

<math>\begin{align}

x &\equiv a_1 \pmod{m_1}, \\
x &\equiv a_2 \pmod{m_2}, \\
  &\vdots \\
x &\equiv a_k \pmod{m_k}

\end{align}</math>

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

計算法

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

直接計算による方法

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

<math>x \equiv 2 \pmod{3},</math>

<math>x \equiv 3 \pmod{5},</math>

<math>x \equiv 2 \pmod{7}</math>

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

3j₁ ≡ 1 (mod 5).

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

j₁ ≡ 2 (mod 5)

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

15j₂ + 8 ≡ 2 (mod 7)

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

j₂ ≡ -6 (mod 7).

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

j₂ ≡ 1 (mod 7)

と書き直せるので、j₂ = 7j₃ + 1 (j₃ ∈ Z) と表せ、これにより x = 105j₃ + 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) それぞれについて、不定方程式

<math>a m + b n = 1</math>

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

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

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

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

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

<math>\begin{align}

-35 &\equiv 1 \pmod{3}, \\
21 &\equiv 1 \pmod{5}, \\
15 &\equiv 1 \pmod{7}.

\end{align}</math>

すると、-35 × 2 + 21 × 3 + 15 × 2 = 23は、先の連立合同式の一つの解であることが容易に確かめられる。しかも定理により解は 3 × 5 × 7 = 105 を法として一意的であったから、すべての解は 23 + 105k (k ∈ Z) と表されることもわかる。つまり、これがこの問題の一般解である。また、この方法を一般化させると、中国の剰余定理の一つの証明を得ることができる。

定理の一般化

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

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

<math>\begin{align}

x &= a_1 \pmod{I_1}, \\
x &= a_2 \pmod{I_2}, \\
  & \vdots \\
x &= a_k \pmod{I_k}

\end{align}</math>

を満たす x ∈ R が、イデアル <math>\textstyle I = \cap_{i=1}^k I_i </math> を法として一意的に存在する。さらに対応

<math>x + I \leftrightarrow (a_1 + I_1, a_2 + I_2, \ldots , a_k + I_k)</math>

によって、環の同型

<math>R/I \cong \bigoplus_{i=1}^k R/I_i</math>

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

<math>I_1 I_2 \cdots I_k \supset \cap_{i=1}^k I_i </math>

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

<math>I_1 I_2 \cdots I_k = \cap_{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)k[X] \cong \bigoplus_{i=1}^l k[X]/(X-a_i)^{n_i}k[X].</math>

関連項目

• RSA暗号

外部リンク

• 孫子算経（原文） (UTF-8)
• 中国の剰余定理
• 中国の剰余定理　解説 (PDF)

• 鬼谷算（きこくさん）