剰余・GCD・逆元・合同方程式
バグ・不具合を報告
整数と法の条件から剰余・最大公約数・逆元・合同解の周期を正確に求める。
負の整数も入力できます。剰余と合同解は非負に正規化し、端数処理は行いません。
入力すると自動で計算します。Enterで次の項目へ進めます。次の入力欄を選んで進めます。
計算結果
—
- 解の周期(法)
- —
- 最大公約数 gcd(a, m)
- —
必要な値を入力すると自動で計算します。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
剰余 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。