2.4.4 中国剰余定理（Chinese remainder theorem)

$n,m$を2つの自然数とします。この項では、$\mod{n}$と$\mod{m}$の関係について考えてみます。ここで、$n,m$を互いに素とします。このとき、次の定理が成り立ちます。

定理 2.4.19 (中国剰余定理（Chinese remainder theorem）)
$n,m$を互いに素$a,b$を任意の整数とするとき、次の方程式を満たす整数$x$が存在し、このような$x$は$\mod{nm}$で一意的に定まる。

$$x \equiv a \pmod{n}$$

$$x \equiv b \pmod{m}$$

証明
合同式 $x\equiv a\pmod{n}$の整数解は、 $a+kn（k:整数）$と表されます。同様に、 $x\equiv b\pmod m$の整数解は $b+sm（s:整数）$と表されます。この解が一致しますので、

$$a+kn=b+sm$$

です。よって、

$$kn-sm=b-a$$

となる整数$k,s$が存在するかどうかが問題となりますが、$n,m$が互いに素であることから、定理2.1.17よりこのような$k,s$が存在することが分かります。

この定理は、2つ以上の合同式に拡張できます。また、証明では、定理2.1.17が使われていることに注意しましょう。定理2.1.17は、初等整数論では最も基本的な定理の1つです。

この定理は、中国剰余定理、又は英語では、Chinese remainder theoremと呼ばれていますが、それは、中国の古代の算術書である孫子算経に書かれていたからです。孫子算経に書かれていたのは上の定理を3方程式の場合に拡張したもので、3で割ると2余り、5で割ると3余り、7で割ると2余る数は如何に?という問題です。

例 2.4.20
3で割ると2余り、5で割ると3余る数を求めてみましょう。 これを合同式で記載すると

$$x \equiv 2 \pmod{3}$$

$$x \equiv 3 \pmod{5}$$

に解ががあるか?ということになります。中国剰余定理を用いると解があることが分かりますが、それは、3,5が互いに素であるからです。具体的に解を求めてみましょう。 3で割って2余る数は、2,5,8,11,14,17,20,23$\cdots$ですね。また、5で割って3余る数は、3,8,13,18,23,28,$\cdots$ですね。したがって、3で割ると2余り、5で割ると3余る数としては、8,23があります。このように、上の合同式の解は、 $x\equiv 8\pmod{15}$であり、$\mod {15}$で一意的に定まります。

例 2.4.21
それでは、割る数が互いに素でないときはどうでしょうか。例えば、2で割ると1余り、4で割ると2余る数はあるでしょうか?

$$x \equiv 1 \pmod{2}$$

$$x \equiv 2 \pmod{4}$$

です。2で割ると1余る数は、1,3,5,7,$\cdots$、つまり奇数ですね。4で割ると2余る数は、2,6,10,14,$\cdots$であり偶数（の一部)です。よって、2で割ると1余り、4で割ると2余る数は存在しません。これは、2,4が互いに素でないために生じている現象です。互いに素でない場合（例えば、2,4の場合)、片方の余り（2で割ったら1余る)からもう片方の余りに制約（4で割ると余りは1,3しかなり得ない)が生じているのです。

上の2つの例から分かる通り、互いに素の場合には、このような制約なくそれぞれ独立して余りを選ぶことができます。これは、$n$と$m$が互いに素の場合、$\mod{n}$と$\mod{m}$の世界が独立であることを意味しています。ここで重要なことは1次式を解く場合に限定していることです。2次式の解の有無については、独立していません。$\mod{n}$と$\mod{m}$の世界が互いに関連しあっていることが分かります。それが相互法則と呼ばれているものです。