一般化中国剰余定理
複数の剰余・法の条件について、互いに素でない場合も含めて共通整数解と周期を求めます。
例の値が入力されています。直接確認するか、値を変更してみてください。
入力はブラウザで処理されます。再読み込みすると例の値に戻ります。
使い方と例
x≡a (mod m), x≡b (mod n); (b−a) mod gcd(m,n)=0; period=lcm(m,n)
x≡2 mod 3、x≡3 mod 5、x≡2 mod 7の最小非負解は23、周期は105です。
最大20条件、入力絶対値1,000,000,000,000以下の整数・法は正数です。BigIntで正確に計算し、合成周期が100桁を超えると拒否します。
よくある質問
法が互いに素でなくても解はありますか?
はい。剰余の差が法の最大公約数で割り切れれば結合できます。不一致なら解なしと表示します。
負の剰余はどう処理しますか?
正の法に対する同じ合同類に正規化します。結果は最小非負解と、すべての解を表す周期です。
計算基準と参考資料
- Stanford: Chinese remainder theorem
互いに素な法の合同式の解と周期。一般化した結合では最大公約数による整合性を追加検査します。