ForHosting KIT · 数学

法 n の原始根の個数を計算

法18の原始根はちょうど2個で、これはオイラーのφを2回適用した値です。法を入れると生成元の個数が分かり、8のように原始根がない場合ははっきりそう伝えます。ブラウザで無料で使えます。

  • 無料
  • ブラウザで動作
  • 登録不要
  • データは端末の外に出ません
ご利用方法 ウェブAPIメールTelegramアプリ 近日
入力した場合
N
18
結果
絶対値
18
原始根の個数
2

この計算機は、指定した法に原始根が存在するかを判定し、存在する場合はその正確な個数を返します。結果は法のオイラー関数にもう一度オイラー関数を適用した値で、phi(phi(n)) と表します。入力が素数であるとは仮定せず、原始根を持つすべての法を扱います。原始根が存在しない種類の法には、誤解を招く 0 ではなく、理由が明確な入力エラーを返します。

計算される個数の意味

法 n の原始根とは、その累乗を順に取ることで、法 n における可逆な剰余類をすべて生成できる剰余類です。群論では、整数の法 n における乗法群の生成元に当たります。このツールが答えるのは、その群を生成する相異なる剰余類がいくつあるかという明確な問いです。

生成元そのものを列挙したり、最小の生成元を探索したりはしません。原始根が存在するとき、乗法群は位数 phi(n) の巡回群です。位数 phi(n) の巡回群には正確に phi(phi(n)) 個の生成元があり、これが返される値です。

たとえば法 18 の可逆な剰余は位数 6 の巡回群を作り、phi(6) は 2 なので、原始根は 2 個です。この個数は任意の整数表現ではなく法 n の剰余類を数えます。n の倍数だけ異なる値は同じ根を表します。

そのため、個々の根より生成元集合の大きさが重要な証明、演習、アルゴリズムで役立ちます。

原始根を持つ法の分類

原始根はすべての正の法に存在するわけではありません。完全な分類定理によると、n が 2、4、奇素数のべき p^k、または奇素数のべきの 2 倍 2p^k の場合に限って存在します。計算機は与えられた法を素因数分解し、個数を求める前にこの定理を適用します。

この確認は重要です。 適格でない法に phi(phi(n)) をそのまま適用すると、生成元が存在しないのに正の値が出てしまうからです。たとえば phi(8) は 4、phi(4) は 2 ですが、法 8 に原始根は存在しません。ここで 2 を返すのは数学的に誤りなので、明示的なエラーにします。

2 より大きい素数は p^1 という特別な場合に含まれ、9、14、18、25 のような合成数も適格です。一方、8、12、15、20 は適格ではありません。分類判定と個数の公式を分けることで、出力が実在する原始根集合の個数を必ず表すようにしています。

入力方法と結果の読み方

2 から 1,000,000,000,000 までの整数 n を入力してください。入力は数値の整数でなければならず、10 進文字列、分数、科学表記による近似値、負数、安全でない JavaScript 整数は受け付けません。上限により素因数分解の処理を有限で予測可能にしながら、学習用から実用まで広い範囲を扱えます。

内部では決定的な試し割りで素数べき構造を求め、存在定理を確認し、異なる素因数から phi(n) を計算して、続いて phi(phi(n)) を計算します。ネットワーク通信も乱数探索も行わないため、同じ入力には常に同じ出力が得られます。根そのものが必要な場合は探索または列挙のツールをご利用ください。

整数論の演習を確認

原始根を手作業で列挙する前に、得られるべき生成元の個数を確認できます。

生成元探索の規模を把握

原始根の全探索で見つかるべき有効な剰余類の数を事前に求められます。

適格な法を検証

後続のアルゴリズムが原始根の存在を仮定する前に、乗法群が巡回群でない法を除外できます。

どの公式を使って計算しますか?

原始根を持つ法について phi(phi(n)) を返します。ここで phi はオイラー関数です。

0 ではなくエラーになるのはなぜですか?

数学的に対象外のケースと有効な個数を区別する仕様だからです。原始根を持たない法は無効な入力として通知します。

どの法が原始根を持ちますか?

正確には 2、4、奇素数のべき p^k、およびその 2 倍である 2p^k です。

原始根そのものも列挙しますか?

いいえ。 法 n において原始根となる剰余類の個数だけを返します。

素数を法として指定できますか?

はい。 2 を含むすべての素数を法として扱えます。奇素数は奇素数べきの一例です。

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

POSThttps://api.kit.forhosting.com/numth/count-primitive-roots

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

curl -X POST https://api.kit.forhosting.com/numth/count-primitive-roots \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":18}'
{
  "n": 18
}
{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.count_primitive_roots",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

HTTPコード意味
401unauthorizedAPIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
402insufficient_balance残高が不足しています。チャージ後に再度お試しください。
404unknown_type指定されたタスクタイプは存在しません。タイプ名を確認してください。
429rate_limitedリクエストが多すぎます。しばらく待ってから再度お試しください。

入力方法と結果の読み方

応答では入力値を modulus として再掲し、primitive_root_count に正確な整数の個数を示します。原始根が存在しないという invalid_input は、一時的な障害ではなく法に関する数学的結論です。この endpoint は個数だけを返します。API リクエストの料金は $0.002 で、常に同じ正確な算術を使います。

API リクエストの料金はいくらですか?

API リクエスト 1 回の料金は $0.002 です。

KITの完全なドキュメントを見る →