中国の剰余定理

中国の剰余定理とは、ある数学の問題とそれに関連した定理の事である。

概要

中国の剰余定理とは、中国大陸で晋の時代、3~4世紀ごろに出版された「孫子算経」という算法に関する書物に記載された問題である。「孫子」と言うが、一般的に孫子として有名な孫武より新しい時代の人であり、直接の関係は無いらしい。

問題の要旨は、未知数Nに対し自然数で割ったあまりの情報だけが与えられていた場合にNの候補を求めると言うものである。記載されていた問題を現代風に書くと次のようになる。

ある整数Nを3で割ったら余りが2、5で割ったら余りが3、7で割ったら余りが2であった。
Nを求めよ。

解法

連立方程式を立てる。

1. N=3x+2
2. N=5y+3
3. N=7z+2

合同で書き換えると以下のようになる。

1. N≡2 (mod 3)
2. N≡3 (mod 5)
3. N≡2 (mod 7)

3変数が媒介変数でどのように表されるかを求めると言う方針。
解及び変数が整数に限られることを利用する。

1.2.より 3x+2=5y+3

両辺二倍して整理　6x=10y+2

4. x=5(-x+2y)+2=5w+2

1.3.より　3x=7z

4.を代入　3(5w+2)=15w+6=7z

5. w=7(z-2w)-6=7(z-2w-1)+1=7v+1

4.5.を代入　N=3x+2=3(5w+2)+2=3(5(7v+1)+2)+2=105v+23

以上より、Nは　(105の倍数)+23　という形に表される。

実際、23は3で割ると2、5で割ると3、7で割ると2あまり、105は3,5,7で割り切れる。

一般の場合

具体的な数を求める問題なのになぜ「定理」と呼ばれるかというと、以下のように一般化する事ができるためである。定理の構造は問題と同じで、自然数で割った余りの情報が与えられている場合、解の候補Nを合同条件の下で一意に求めることができるというものである。解の存在を示す定理なので解を求めるアルゴリズムは別途考える必要がある。

m₁, m₂, …, m_nがどの2つも互いに素な自然数である時、任意の整数の列a₁, a₂, …, a_nに対して

N≡a₁ (mod m₁)
N≡a₂ (mon m₂)
…
N≡a_n (mod m_n)

を満たすNがm₁m₂…m_nを法として一意に存在する。

証明

• n=2の場合

m₁,m₂が互いに素ならユークリッドの互除法より適当な整数x₁,x₂が存在してm₁x₁+m₂x₂=1。
これを合同を使って変形していく。

m₁x₁ ≡ 1 (mod m₂)
m₂x₂ ≡ 1 (mod m₁)

a₁m₂x₂ ≡ a₁ (mod ｍ₁)
a₂m₁x₁ ≡ a₂ (mod m₂)

a₂m₁x₁ + a₁m₂x₂ ≡ a₁ (mod m₁)
a₂m₁x₁ + a₁m₂x₂ ≡ a₂ (mod m₂)

以上より、N≡a₂m₁x₁ + a₁m₂x₂ (mod m₁m₂) と置けば求めたい整数となる。合同の性質からこの解は一意である。

• n>2の場合

数学的帰納法で証明する。あるk>2で、

m₁, m₂, …, m_kがどの2つも互いに素な自然数である時、任意の整数の列a₁, a₂, …, a_kに対して

M≡a₁ (mod m₁)
M≡a₂ (mon m₂)
…
M≡a_k (mod m_k)

となるMがm₁m₂…m_kを法として一意に存在する、と仮定する。

k+1番目の時、

m₁, m₂, …, m_k+1がどの2つも互いに素な自然数である時、整数の列a₁, a₂, …, a_k+1に対して

N≡a₁ (mod m₁)
N≡a₂ (mon m₂)
…
N≡a_k (mod m_k)
N≡a_k+1 (mod m_k+1)

となるNを求めたいが、仮定よりk個の式についてはMを用意すればよく、k+1個の連立方程式は以下の2個の連立方程式に簡略化される。

N≡M (mod m₁m₂…m_k)
N≡a_k+1 (mod m_k+1)

m₁m₂…m_kとm_k+1は互いに素なので、n=2の結果より、連立方程式を満たすNがm₁m₂…m_k+1を法として一意に存在する。

この場合、適当な整数x₁,x₂が存在してm₁m₂…m_kx₁+m_k+1x₂=1、
N≡a_k+1m₁m₂…m_kx₁ + Mm_k+1x₂ (mod m₁m₂…m_k+1) である。

さらに一般の場合

この定理は整数だけではなく一般の可換環に対しても拡張する事ができる。整数は可換環の一種である。

I₁, I₂, …, I_nが環Aのイデアルでどのi,jに対しても1∈I_i+I_jであるとき、
I₁∩I₂∩…∩I_n=I₁I₂…I_nで、次の同型写像ができる。

A/(I₁∩I₂∩…∩I_n)≅A/I₁×A/I₂×…×A/I_n

このままでは抽象的すぎて何を言っているか分からないので、大雑把だが解説する。

• イデアルとは倍数や素数といった概念を一般化したものである。
• 1∈I_i+I_jはI_iとI_jが「互いに素」であることを示している。
• I₁∩I₂∩…∩I_n=I₁, I₂, …, I_nは、互いに素な数の最小公倍数が単純な積であらわされることに対応する。
• A/IはイデアルIによるAの剰余類であり、Iを法とした合同関係の式に対応している。
• A/I₁×A/I₂×…×A/I_nは、各数を法とした合同関係の式を複数用意する事に対応している。
• A/(I₁∩I₂∩…∩I_n)は各数の最小公倍数を法とした合同関係に対応している。
• A/(I₁∩I₂∩I_n)≅A/I₁×A/I₂×…×A/I_nとは両辺の集合の構造が一致しているということに対応している。

以上を踏まえてよく見比べてみると、整数に対する定理と基本的な構造はだいたい同じであることが分かる。

この定理の同等な表現はいろいろあり、整数の場合に近い表現は以下のようになる。

環AのイデアルI₁,I₂,…I_nはどの2つも互いに素であるとする。
Aの元を任意にn個用意する。選んだ元a₁,a₂,…,a_nに対して、

x ≡ a_i (mod I_i)　(1≦i≦n)

を満たすAの元xが、I₁∩I₂∩…∩I_nを法として一意に存在する。

この定理から、105で割ったあまりと3,5,7それぞれで割ったあまり(の直積)の構造が環として一致し、105で割ったあまりｐを任意に指定すれば対応する3,5,7で割ったあまりq₁,q₂,q₃が、q₁,q₂,q₃を任意に指定すれば対応するpが必ず求まる、という事がわかる。

環の定理の証明を踏まえた別解は以下のようになる。詳しい証明は環の記事を参照。

解法

• J_i=m₁m₂…m_n/m_iをもとめる。

3×5=15､5×7=35、7×3=21

• 1=x₁J₁+x₂J₂+…+x_nJ_nとなるようx₁,x₂,…,x_nをもとめる。

1=35×2-3×23=35×2-(3×(5×3-7×2))×23=35×2-15×69+21×46

• x=a₁x₁J₁+a₂x₂J₂+…+a_nx_nJ_nに代入。これはx ≡ a_i (mod m_i)　(1≦i≦n)を満たす。

x=2×35×2-3×15×69+2×21×46=-1033=105×(-10)+23

求める解は23。

関連項目

• 数学
• 整数
• 剰余、余り
• 合同
• 環(数学)