中国剰余定理（CRT）計算機 ― 連立合同式を解く
x ≡ a₁ (mod n₁)、x ≡ a₂ (mod n₂)…といった連立合同式を中国剰余定理で解く計算機。法が互いに素であるかを自動で検証し、最小の非負整数解と一般解を求めます。
計算例：孫子算経の「物不知其数」問題
中国剰余定理の起源とされる、3〜5世紀頃の中国の算術書『孫子算経』に記された古典的な問題です。「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」という設問に対する答えは、105を法として23になります。
| 条件1 | x ≡ 2 (mod 3) |
|---|---|
| 条件2 | x ≡ 3 (mod 5) |
| 条件3 | x ≡ 2 (mod 7) |
| 解 | x ≡ 23 (mod 105) |
Tips
- 法（nᵢ）どうしが互いに素でない場合はエラーになります。例えば mod 4 と mod 6 は最大公約数が2のため、この計算機では解けません（一般化中国剰余定理が必要なケースです）。
- 余り aᵢ が法 nᵢ 以上や負の値でも、内部で自動的に mod nᵢ に正規化してから計算するため、そのまま入力して構いません。
- 合同式は2〜5個まで追加できます。3個以上の条件を同時に満たす数を探す「福引の当選番号」のような問題にも応用できます。
- 結果の一般解は x ≡ 解 (mod N) の形で表示されます。N の整数倍を足したどの数も、同じ条件をすべて満たします。
よくある質問
余談ですが ― 「3世紀の算術書」から「RSA暗号の高速化」まで
中国剰余定理の起源は、3世紀から5世紀頃に成立したとされる中国の算術書『孫子算経（そんしさんけい）』に記された「物不知其数（物、其の数を知らず）」という問題にさかのぼります。「3で割ると2余り、5で割ると3余り、7で割ると2余るものは何個あるか」という設問は、複数の割り算の余りから元の数を逆算するという、現代のCRTと本質的に同じ発想をすでに示していました。
中国剰余定理が現代でもっとも実用的に使われている場面の一つが、RSA暗号における復号処理の高速化です。RSA暗号の復号は「巨大な数を秘密鍵でべき乗して法で割った余りを求める」処理ですが、法として使われる合成数 n = p × q（p, q は大きな素数）をそのまま使う代わりに、CRTを使って mod p と mod q それぞれで独立に計算してから結果を統合すると、理論上は最大で4倍程度の速度向上が見込めます。これは「CRT-RSA」と呼ばれ、多くの暗号ライブラリで実装されている最適化手法です。
本ツールが対応するのは、法がすべて互いに素である「古典的な中国剰余定理」です。法が互いに素でない場合（例えば mod 4 と mod 6 のように公約数を持つ場合）にも条件次第で解が存在することがありますが、その判定と計算には一般化された拡張版のアルゴリズムが必要になるため、本ツールのスコープ外としています。