原始根計算機 — nを法とする最小の原始根を求める
この原始根計算機は、nを法とする最小の原始根 — 累乗g¹, g², g³, ...が繰り返す前にmod nのすべての単位を巡回する整数g — を求めます。まず原始根がそもそも存在するかどうかを確認します（n = 1, 2, 4, pᵏ、または奇素数pに対する2pᵏの場合にのみ存在します）。その後、オイラーのトーシェント関数とその素因数分解を使用して各候補を効率的にテストします。
クイック回答
原始根g mod nは、その累乗によってmod nのすべての単位を生成します。以下にnを入力すると、原始根がそもそも存在するかどうかの自動チェックとともに、最小のものが見つかります。
原始根計算機 — mod nの生成元を求めるの使い方
- 1
正の整数n（最大1,000,000）を入力します。
- 2
「計算」をクリックして、存在する場合、nを法とする最小の原始根を求めます。
- 3
検証に使用されたφ(n)とφ(n)の素因数を確認します。
なぜ原始根計算機 — mod nの生成元を求めるを使うのか？
nを法とする原始根は、乗算のもとでnと互いに素な整数の群の生成元です：その連続する累乗は、正確にφ(n)ステップで1に戻る前に、mod nのすべての単位を正確に1回ずつ生成します。すべてのnがそれを持つわけではありません — 原始根は、n = 1, 2, 4、奇素数のべき乗pᵏ、または奇素数のべき乗の2倍2pᵏに対してのみ存在します。これは数論における古典的な結果です。この計算機はまずその条件を確認し、次にφ(n)の各素因数qに対してg^(φ(n)/q) mod nをテストすることで各候補gを効率的に検証します — これらのテストのいずれも1に等しくない場合に限り、gは原始根です。
よくある質問
関連ツール
オイラーのトーシェント関数計算機 — φ(n)をオンラインで
素因数分解を通じて、オイラーのトーシェント関数φ(n) — nと互いに素な1からnまでの整数の数 — を計算します。完全な因数分解を表示する無料計算機。
モジュラー指数計算機 — 高速なbᵉ mod mをオンラインで
高速な二乗・乗算指数計算を使用して、任意に大きな指数に対するbᵉ mod mを計算します。暗号学に不可欠なBigInt精度を備えた無料計算機。
モジュラー乗法逆元計算機 — ax ≡ 1 (mod m) を解く
拡張ユークリッドアルゴリズムを使用して、a のモジュラー乗法逆元をモジュラスmで求めます。BigInt精度と存在チェックを備えた無料計算機。
群論位数電卓 — ℤₙにおける元の位数をオンラインで
(ℤₙ, +)または(ℤ/nℤ)ˣにおける元の位数を求め、ラグランジュの定理の整除性チェックをステップとして表示します。無料電卓、即座に結果が得られます。