中国剰余定理（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) |
中国剰余定理（CRT）とは
中国剰余定理は、**「3で割ると2余り、5で割ると3余り、7で割ると2余る数は何か」**のような連立合同式を解く定理です。法がすべて互いに素であれば、法の積を法とする範囲でただ1つの解が定まります。このツールは合同式を最大5本まで入れて、最小の非負整数解と一般解を求めます。
**このツールは法がすべて互いに素な「古典的な」形だけを扱います。**どれか2つの法に1より大きい公約数があると解けないため、その旨のエラーになります（互いに素でない場合の一般化中国剰余定理はスコープ外です）。**法は2以上の整数**で、余りは自動で0以上その法未満に正規化されるため、法以上の値や負の値を入れても構いません。内部は多倍長整数なので桁数の制限はありません。
中国剰余定理計算機の使い方
- 余りと法を入力する 1本の合同式ごとに余り a と法 n を入れます。x ≡ a (mod n) の形に対応します。
- 合同式を増やす 「合同式を追加」で最大5本まで並べられます。本数が増えると解の一意性が保たれる範囲（法の積）も大きくなります。
- 解を求める 「解く」を押すと、最小の非負整数解と、法の積を法とする一般解が出ます。
- 計算過程を追う 各合同式について Nᵢ（法の積から自分の法を除いたもの）と Mᵢ（Nᵢ の逆元）が並びます。手計算の答え合わせに使えます。
- 互いに素でないと解けない 「法が互いに素でない」と出たら、たとえば 4 と 6 のように公約数を持つ法が混じっています。組み合わせを見直してください。
使いこなすためのヒント
- 法（nᵢ）どうしが互いに素でない場合はエラーになります。例えば mod 4 と mod 6 は最大公約数が2のため、この計算機では解けません（一般化中国剰余定理が必要なケースです）。
- 余り aᵢ が法 nᵢ 以上や負の値でも、内部で自動的に mod nᵢ に正規化してから計算するため、そのまま入力して構いません。
- 合同式は2〜5個まで追加できます。3個以上の条件を同時に満たす数を探す「福引の当選番号」のような問題にも応用できます。
- 結果の一般解は x ≡ 解 (mod N) の形で表示されます。N の整数倍を足したどの数も、同じ条件をすべて満たします。
中国剰余定理が役立つ場面
整数論の演習や試験対策
手で解いた答えの確認に使えます。Nᵢ・Mᵢ の中間値も出るので、どこで間違えたかを絞れます。
暗号のアルゴリズムを学ぶとき
RSAの復号を高速化する CRT 最適化は、この定理をそのまま使っています。仕組みを数値で追えます。
周期の重なりを求めるとき
異なる周期で繰り返す事象が同時に起こる時刻は、連立合同式として表せます。
古典的な問題を再現するとき
『孫子算経』の「物不知其数」（3で2余り、5で3余り、7で2余る数）は 105 を法として 23 です。そのまま入れて確かめられます。
関連する整数論の道具を使いたいとき
逆元や合同式そのものは合同式・モジュラー計算、最大公約数は最大公約数・最小公倍数、素因数分解は素因数分解で扱えます。
中国剰余定理に関する用語集
- 中国剰余定理（CRT）
- 法が互いに素な連立合同式に、法の積を法として一意な解が存在することを述べる定理です。
- 合同式
- x ≡ a (mod n) の形の式で、「x を n で割った余りが a に等しい」ことを表します。
- 法（modulus）
- 割る数のことです。このツールでは2以上の整数に限ります。
- 互いに素
- 2つの整数の最大公約数が1であることです。古典的なCRTはどの2つの法を取っても互いに素であることを要求します。
- ペアワイズ互いに素
- 3つ以上の数について、どの2つを取り出しても互いに素であることです。全体の最大公約数が1でも、ペアワイズでない場合があります。
- モジュラー逆元
- a·x ≡ 1 (mod n) を満たす x です。CRT では Nᵢ の逆元 Mᵢ を求める場面で使います。
- 拡張ユークリッドの互除法
- 最大公約数と同時にベズー係数を求める算法です。モジュラー逆元の計算に使われます。
- 一般解
- 最小の非負整数解に法の積の整数倍を足したものすべてです。x ≡ 23 (mod 105) のような形で表します。
よくある質問
余談ですが ― 「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 のように公約数を持つ場合）にも条件次第で解が存在することがありますが、その判定と計算には一般化された拡張版のアルゴリズムが必要になるため、本ツールのスコープ外としています。