中国の剰余定理

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

概要

中国の剰余定理とは、中国大陸の晋の時代、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≡3 (mod 2)
2. N≡5 (mod 3)
3. N≡7 (mod 2)

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

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あまる。

一般の場合

具体的な数を求める問題なのになぜ「定理」と呼ばれるかというと、以下のように一般化する事ができるためである。定理の構造は問題と同じで、自然数で割った余りの情報が与えられている場合、解の候補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 ｍ₁)
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₂, …, ak+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) である。

関連項目

• 数学
• 整数
• 剰余、余り
• 合同