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

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

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

中国の剰余定理

m1，m2 を互いに素な正整数（即ち最大公約数が１）とする。a1，a2 を整数する。 このとき，

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

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

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

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

　具体例挙げます。

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 を１つ求める。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 がその１つの解になります。従って，

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)

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

4543973281=67409*73679

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

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

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

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

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

ｘ ≡ 123456789 (mod 4543973281)

が得られます。

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

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

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

まとめ

　中国の剰余定理は，

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

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

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