中国剰余定理計算機

中国剰余定理は CRT とも呼ばれ、複数の剰余条件を一つの解にまとめます。例えば x ≡ 2 modulo 3 は、x を 3 で割ると余りが 2 になることを意味します。この計算機は三つの合同式を受け取り、すべてを同時に満たす最小の非負整数を求めます。 古典的な定理は、どの二つの法も互いに素、つまり各組の最大公約数が一である場合に適用できます。この条件では、法の積を法として解がちょうど一つ存在します。法が 3、5、7 の場合、その積は 105 です。最小の解が 23 なら、23、128、233、さらに 105 を加減して得られるすべての整数が同じ連立合同式を満たします。 構成的なアルゴリズムでは、まずすべての法を掛けて M を求めます。各式について M をその法で割り、部分積を作ります。法はどの二つも互いに素なので、この部分積は除いた法に関する乗法逆元を持ちます。各余り、部分積、逆元を掛けると、一つの合同式を満たし、ほかの法では零になる項ができます。それらを足し合わせて M で剰余を取ると答えが得られます。 CRT は教科書の数論以外にも広く応用されます。大きな整数の効率的な演算、暗号実装、符号理論、暦の周期、交代勤務の予定、数式処理、剰余からの値の復元などに使われます。難しい計算を複数の法における小さな独立した計算に分け、後で結合できる場合に特に有効です。 整数の余りと、一より大きい法を入力してください。余りは負の数でも法より大きくても構いません。剰余演算で自動的に正規化されます。この版では標準的な定理に合わせ、一意な剰余類を保証するため、法がどの二つも互いに素であることを必須としています。互いに素でない法でも解ける場合はありますが、追加の整合性確認が必要なため対象外です。得られた解を各法で割り、余りを調べて必ず確認してください。