一般化中国剰余定理

複数の剰余・法の条件について、互いに素でない場合も含めて共通整数解と周期を求めます。

例の値が入力されています。直接確認するか、値を変更してみてください。

入力はブラウザで処理されます。再読み込みすると例の値に戻ります。

結果

使い方と例

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桁を超えると拒否します。

よくある質問

法が互いに素でなくても解はありますか?

はい。剰余の差が法の最大公約数で割り切れれば結合できます。不一致なら解なしと表示します。

負の剰余はどう処理しますか?

正の法に対する同じ合同類に正規化します。結果は最小非負解と、すべての解を表す周期です。

計算基準と参考資料

計算基準の確認: · 計算・検証原則 · エラー報告