法 n のべき等元計算機
法12では、2乗しても変わらない剰余が0、1、4、9の4つあります。1兆までの法を入力すると、べき等元の完全な一覧を小さい順に返し、その個数を説明する素数べきの分解も示します。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- N
- 12
- 冪等元
- 0, 1, 4, 9
- 数量
- 4
- 素数べきの因数
- 4, 3
法 n のべき等元とは、自分自身を掛けても変化しない剰余、つまり x の2乗が法 n で x と合同になるものです。この計算機は個数や一例だけでなく、0 から n − 1 までの完全な一覧を昇順で返します。法を互いに素な素数べきへ分解し、中国剰余定理によって各解を厳密に構成します。応答には素数べき因子も含まれるため、結果の確認、教材での説明、テスト、別の合同算術処理への再利用を容易に行えます。
べき等剰余の意味
定義式は x² ≡ x（mod n）であり、n が x(x − 1) を割り切ることと同値です。0 と 1 は、2乗しても剰余類が変わらないため、必ず解になります。合成数を法とする場合は、n の異なる素数べき部分が隣り合う x と x − 1 を別々に割り切れるので、ほかの解も存在します。
たとえば法 12 の完全な一覧は 0、1、4、9 です。16 と 4 の差は 12 なので 4 は解であり、81 と 9 の差は 72 なので 9 も解です。idempotents 配列には 0 以上 n − 1 以下の標準代表元だけが重複なく数値順で入ります。
count は個数を示します。n が 1 の場合、剰余類は 0 で表す1個だけで、これもべき等です。
完全な一覧を構成する方法
最初に n を極大な素数べきへ因数分解します。各因子は互いに素で、積は n です。素数べきを法とする x² ≡ x の剰余類は 0 と 1 の2個だけです。
中国剰余定理により、各因子について 0 または 1 を独立に選ぶと、法 n の剰余類がただ1つ定まります。n に異なる素数が k 個あれば、べき等元は 2^k 個です。本計算機は 0 から n − 1 までを総当たりしません。
各素数べき q に対して n/q とその法 q における正確な逆元を求め、すべての二進選択に応じて CRT 基底を結合し、法 n で簡約して並べ替えます。因数分解は決定的な試し割りで行い、CRT の積と逆元には BigInt を使うため丸め誤差がありません。通信、時計、乱数、可変キャッシュは使用しないため、同じ入力には常に同じ結果を返します。
法の指定と応答の利用方法
公開上限の1兆を超える値も、高負荷な探索を始める前に拒否します。count が異なる素因数の個数を指数とする2の累乗か確認できます。n が 1 の場合だけは因子が空で個数は1です。
各 x について、x と x の積から x を引いた値を n で割った非負剰余が0か調べれば検算できます。有限環の処理、ライブラリのテスト、中国剰余定理の採点、合同計算の列挙に利用できます。
活用例
中国剰余定理の学習
各素数べきで独立に 0 または 1 を選ぶと、合成数を法とする具体的な剰余になる仕組みを示します。
合同算術コードのテスト
環、合同式、剰余類の実装を検証するための、正確で整列済みのテスト基準を生成します。
有限環の構造の調査
法 n の整数環で、乗法に関して射影のように振る舞う要素をすべて列挙します。
よくある質問
0 と 1 は必ず含まれますか？
はい、どちらも常にべき等です。n が 1 の場合、この2つの名前は唯一の標準剰余 0 を表します。
べき等元はいくつありますか？
n が 1 より大きく、異なる素因数が k 個なら、正確に 2^k 個です。法 1 の剰余類は1個です。
なぜ素数べきを返すのですか？
中国剰余定理で使う互いに素な成分を示し、解の個数の理由を明確にするためです。
すべての剰余を試すのですか？
いいえ。 n を因数分解し、CRT 基底を用いて完全な集合を直接構成します。
法12のべき等元は何ですか？
0、1、4、9です。例えば4の2乗は16で、12で割った余りは4、9の2乗は81で余りは9です。12は異なる素因数を2つ持つので、べき等元は4つになります。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/idempotents-mod-n \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":12}'const res = await fetch("https://api.kit.forhosting.com/numth/idempotents-mod-n", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 12
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/idempotents-mod-n",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 12
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/idempotents-mod-n", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":12}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":12}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/idempotents-mod-n", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"n": 12
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.idempotents_mod_n",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_n | 1000000000000 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
べき等剰余の意味
prime_power_factors は計算に使った構造を示し、12 は 2、2、3 ではなく 4、3 と表されます。したがって、候補1個の判定ではなく全解が必要な場合に適しています。
完全な一覧を構成する方法
上限を1兆にすることで処理時間を予測可能にし、返す値を安全な JSON 整数に保ちます。
法の指定と応答の利用方法
n を正の JSON 整数または単純な10進整数文字列として指定してください。説明的なフィールド名を使うフォーム向けに modulus という別名も受け付けます。文字列の先頭のプラス記号は許可されますが、分数、指数表記、16進接頭辞、空白、負数、0、欠落値、配列、不適切なオブジェクトは invalid_input になります。成功時は idempotents が完全な昇順一覧、count がその個数、prime_power_factors が互いに素な分解を表します。成功した API リクエストの料金は $0.002 で、無料のブラウザー版も同じ純粋関数を実行します。
技術的な質問
どの入力が拒否されますか？
欠落値、整数でない値、1 未満の値、不正な10進文字列、公開上限を超える法は invalid_input になります。