剰余・GCD・逆元・合同方程式

整数と法の条件から剰余・最大公約数・逆元・合同解の周期を正確に求める。

負の整数も入力できます。剰余と合同解は非負に正規化し、端数処理は行いません。

入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。

計算する内容

符号付き10進整数。数字256桁まで。空欄は0として扱いません。

法は正の整数。逆元では2以上が必要です。


計算結果

必要な値を入力すると自動で計算します。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

剰余 r = ((a % m) + m) % m(0≦r<m)。GCD はユークリッド互除法。逆元は gcd(a,m)=1 の場合のみ拡張ユークリッド法で求めます。一次合同式 a×x≡b (mod m) は g=gcd(a,m) が b を割り切るとき解があり、x≡x₀ (mod m/g)。連立合同式は条件を順に結合し、rᵢ−rⱼ が gcd(mᵢ,mⱼ) の倍数でない場合は無解。解があれば x≡x₀ (mod lcm(m₁,…,mₖ))。

非負剰余、最大公約数、逆元、一次合同式・連立合同式の代表解と周期、無解の判定。

計算例(架空の数値)

例:−17を5で割った非負剰余は3。gcd(486,270)=54。17の法43における逆元は38。6x≡8 (mod 14) の解は x≡6 (mod 7)。x≡1 (mod 3)、x≡2 (mod 4)、x≡8 (mod 10) の解は x≡58 (mod 60)。

適用対象と限界

整数を用いる合同演算・周期条件の計算。固定ビット幅の整数表現、浮動小数点、非整数の方程式、離散対数、素因数分解、秘密鍵の生成・暗号鍵の安全性評価は対象外。。

採用した方式

  • 整数合同演算と一般化中国剰余定理(整数演算 v1.0):対象範囲 10進の符号付き整数、1以上の法、逆元は法2以上、最大12条件・各256桁/適用地域 global

方法と出典

方法:正規化剰余/拡張ユークリッド互除法/一般化中国剰余定理 v1.0(2026-11-13照合)。データ記録日:2026-11-13。