中国の剰余定理
(Chinese Remainder Theorem)

  ここでは「整数の合同と1次合同式」に続いて,中国の剰余定理について説明します。

 整数の合同は a ≡b  (mod m) の形のものでした。そして「整数の合同と1次合同式」の項では1つのmを固定し考えましたが,いくつかの m で合同を考えることは時には有用なこともあります。中国の剰余定理は互いに素な m1 と m2 に対しての連立合同式の解に関するものです。

中国の剰余定理

m1,m2 を互いに素な正整数(即ち最大公約数が1)とする。a1,a2 を整数する。 このとき,

x ≡a1  (mod m1)
x ≡
a2  (mod m2)

を満たす整数 x が m1m2 を法にして唯ひとつ存在する。

 この定理が中国の剰余定理と言われるのは,2世紀頃の中国の算術書「孫子算経」にこの性質の記述があることに由来します。そのことからまた孫子の定理と言われることもあります。

 今の場合は2つの連立合同式ですが,全く同様にして,3個以上の連立合同式についての定理が得られます。この場合も中国の剰余定理と呼ばれます。

 具体例挙げます。

x ≡ 5 (mod  7 )
x ≡ 3 (mod 11)

の解として x ≡ 47 (mod 77) を得ます。




(中国の剰余定理の証明)

 この定理の証明はいくつもありますが,ここでは実際の解を計算する法を与える証明を挙げます。

(一意性)x1,x2 共に解であったとすると,

x1 ≡ a1 ≡x2 (mod m1)
x1 ≡ a2 ≡x2 (mod m2)

より,x1 ≡x2 (mod m1m2)となり,m1m2を法として 唯ひとつであることが分かる。

(存在) x=a1+bm1と置いて,x ≡ a2 (mod m2) を満たすように b が決められれば,x が実際の解になる。そこで,m1y≡ 1 (mod m2) を解き,y を1つ求める。m1 と m2 が互いに素だから,このようなyは存在し,ユークリッドの互除法を用いて,実際に効率的に求めることが出来る。このy を使って, b=(a2-a1)y としたものが求めるものとなる。

実際,x=a1+bm1 より,x ≡ a1 (mod m1)であり,x=a1+bm1=a1+(a2-a1)y m1≡a1+(a2-a1)≡a2となる。
 


 上の証明の方法で,

x ≡ 5 (mod  7 )
x ≡ 3 (mod 11)

の解を求めて見ましょう。まず,7y≡1(mod 11) を解きます。y=8 がその1つの解になります。従って,

x=5+b*7=5+(3-5)*8*7=-107≡47 (mod 77) が得られます。

プログラム

m1,m2 ,a1,a2 を 入力したとき,

x ≡a1  (mod m1)
x ≡
a2  (mod m2)

を満たす整数 x を出力するプログラム。

 このプログラムを実現する関数 Chinese は次のように簡単に書けます。


Function Chinese(a1,a2,m1,m2)
   Call ExGCD(m1,m2,y,t,c)
   if c<>1 then Print "Error!"
   x = a1 + (a2-a1)*y*m1
   while x<0: x=x+m1*m2:wend
   Chinese = x
End Function

 ここでも拡張ユークリッド互除法 ExGCD を使用しています。

実際にこの関数を使って上の例を計算するには,例えば

a1=5 : m1=7
a2=3 : m2=11
Print Chinese(a1,a2,m1,m2)
End

Function Chinese(a1,a2,m1,m2)
...

Sub ExGCD(a,b,s,t,c)
...

とします。

中国の剰余定理の応用例

 中国の剰余定理を使う例としては,次のような状況があります。例えば,

≡ 3053293694 (mod 4543973281)

を解くとします。これを素朴な方法で1から順に試して行くと最大4543973280回の試行を行うことになります。 これはいくら計算機でも膨大な回数になります。しかし,ここで,

4543973281=67409*73679

と素因数分解されることに注意して,連立方程式

≡ 3053293694 ≡ 3039 (mod 67409)
≡ 3053293694 ≡ 35934 (mod 73679)

を解くことにします。この方程式を素朴な方法で解を試行して求めると,

x ≡ 30910 (mod 67409)
x ≡ 44464 (mod 73679)

が得られます。この程度の計算なら, Tiny Basic でも数秒で可能です。これについて,中国の剰余定理を適用すると,

x ≡ 123456789 (mod 4543973281)

が得られます。


 このことを更に一般的に考えてみると,次のことが分かります。

mが互いに素な小さい数の積に分解されるとmを法とする合同の問題は,

少なくとも計算問題としては,簡単な問題になる。

まとめ

 中国の剰余定理は,

mを法とする合同の問題は

mの素因数分解にあらわれる素べき部分への問題に還元できる

ことを示しています。これは計算法だけでなく,理論的にも重要な事柄です。この定理は初等整数論だけでなく,整数論一般でしばしば使われる重要な定理です。