中国剰余定理とは？
中国剰余定理（CRT：Chinese Remainder Theorem）は、整数論における古典的な定理です。\(x \equiv a_1 \pmod{m_1}\)、\(x \equiv a_2 \pmod{m_2}\)、… という連立合同式があり、それぞれの法（mod の数）が互いに素（共通の約数を持たない）であるとき、\(M = m_1 \cdot m_2 \cdot \ldots\) を法として、ただ一つの解 \(x\) が存在することを保証します。この計算機は、その中で最小の非負の解を求めます。
この計算機の使い方
各余り \(a_i\) と、その法 \(m_i\) をペアで入力してください。2 元または 3 元の連立合同式に対応しており、2 つだけ解きたい場合は 3 つ目の法を空欄のままにします。本ツールはまず法どうしが互いに素かを確認したうえで、解 \(x\) と合成された法 \(M\) を返します。なお、\(x + Mk\)（\(k\) は任意の整数）の形で表されるすべての値も解になります。
計算式の解説
\(M = \prod m_i\) とします。各合同式について \(M_i = M / m_i\) を定義し、さらに \(y_i = M_i^{-1} \bmod m_i\)（拡張ユークリッドの互除法で求める法逆元）とします。解は重み付き和 $$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$ で与えられます。\(M_i\) は \(m_i\) 以外のすべての法で割り切れるため、各項は自分自身の合同式に対してだけ正しい余りを与えます。
計算例
\(x \equiv 2 \pmod{3}\) かつ \(x \equiv 1 \pmod{4}\) を解いてみましょう。ここで \(M = 3 \cdot 4 = 12\) です。\(M_1 = 4\) であり、\(4 \equiv 1 \pmod{3}\) なので \(y_1 = 1\)。\(M_2 = 3\) であり、\(3 \equiv 3 \pmod{4}\) なので \(y_2 = 3\)（\(3 \cdot 3 = 9 \equiv 1\) となるため）。よって $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ 5 (mod 12)。検算：\(5 \bmod 3 = 2\) ✓、\(5 \bmod 4 = 1\) ✓。
よくある質問（FAQ）
なぜ法は互いに素でなければならないのですか？ 2 つの法が共通の約数を持つ場合、連立合同式は解を持たないこともあれば、それらの最小公倍数を法として複数の解を持つこともあります。このとき標準的な CRT の公式は適用できません。
「最小の非負の解」とは何ですか？ すべての解は \(M\) の倍数だけずれて存在します。この計算機は、その中で 0 から \(M-1\) の範囲にある解を表示します。
負の余りを入力できますか？ はい。負の値は計算前に各 \(m_i\) を法として 0 から \(m_i-1\) の範囲に正規化されます。
