§A4.6中国剰余定理

1 2つの条件をまとめる

まず$x \equiv 2 \pmod 3$と$x \equiv 3 \pmod 5$の2条件を1つにまとめます。$3$と$5$は互いに素なので、ベズーの等式$3u + 5v = 1$を満たす整数$u, v$が存在します。$u = 2, v = -1$（$3\times 2 + 5\times(-1) = 1$）ととれます。ここで

$$x = 2 \times 5 \times (-1) + 3 \times 3 \times 2 = -10 + 18 = 8$$

とおくと、$5v = 1 - 3u \equiv 1 \pmod 3$なので$x \equiv 2 \times 1 = 2 \pmod 3$、同様に$3u \equiv 1 \pmod 5$なので$x \equiv 3 \times 1 = 3 \pmod 5$——両方の条件を同時に満たします。$x \equiv 8 \pmod{15}$が2条件の答えです。

2 中国剰余定理

いま行った操作を一般化したのが中国剰余定理です。

$m, n$が互いに素なとき、$x \equiv a \pmod m$かつ$x \equiv b \pmod n$を満たす$x$が、法$mn$のもとでちょうど1つ存在する。

存在は先ほどと同じ構成です。$mu + nv = 1$となる$u, v$を（互いに素だから）ベズーの等式で取り、$x = anv + bmu$とおけば、$nv \equiv 1 \pmod m$より$x \equiv a \pmod m$、$mu \equiv 1 \pmod n$より$x \equiv b \pmod n$が同時に成り立ちます。一意性は、$x, x'$がともに条件を満たすなら$x - x'$は$m$でも$n$でも割り切れ、$m, n$が互いに素だから積$mn$でも割り切れる（互いに素な数の倍数を両方満たすなら積の倍数、という事実による）ことから、$x \equiv x' \pmod{mn}$が出ます。

3 3条件への拡張

最初の問題に戻ります。$x \equiv 8 \pmod{15}$と、残りの条件$x \equiv 2 \pmod 7$を、同じ手順でもう一段まとめます。$15$と$7$は互いに素で、$15 \times 1 + 7 \times(-2) = 1$なので$u = 1, v = -2$。

$$x = 8 \times 7 \times (-2) + 2 \times 15 \times 1 = -112 + 30 = -82 \equiv 23 \pmod{105}$$

——答えは$23$（法$105 = 3\times5\times7$のもとで一意）です。実際$23 = 3\times7+2 = 5\times4+3 = 7\times3+2$と、3条件すべてを満たしています。

4 法が互いに素でないとき

法が互いに素でない場合、中国剰余定理はそのままでは使えません。$x \equiv a \pmod m$と$x \equiv b \pmod n$が両立するのは$a \equiv b \pmod{\gcd(m,n)}$のときに限られ、両立すれば解は法$\mathrm{lcm}(m,n)$のもとで一意に定まります（互いに素な場合はこの条件が自動的に満たされ、$\mathrm{lcm}(m,n)=mn$に戻ります）。

5 応用：大きな数を「小分けにして」計算する

中国剰余定理は現代の計算機にも直結しています。巨大な整数の演算を1つの大きな法で行う代わりに、いくつかの小さい互いに素な法で並列に計算し、最後に中国剰余定理で1つの答えに復元する、という技法です。多倍長演算のライブラリや、 RSA 暗号の復号（法$n=pq$での計算を、法$p$・法$q$それぞれで行ってから CRT で合成する）では、この方法で計算量が大きく減ることが知られています。「大きな世界の計算」を「小さな世界の計算の組み合わせ」に分解する、という発想そのものが実装レベルで生きている例です。