オイラー・ヤコビ偽素数判定
561は底2のオイラー・ヤコビ偽素数です。指数280のべき乗の余りが1で、ヤコビ記号と一致しますが、561は合成数です。奇数の合成数と底を入れると、判定の根拠となる各値が分かります。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- N
- 561
- A
- 2
- Gcd
- 1
- ヤコビ記号
- 1
- 指数
- 280
- 余り
- 1
与えられた底に対するオイラー・ヤコビ偽素数とは、素数であるかのようにオイラーの判定条件を満たす奇合成数です。互いに素な底 a については、a の (n 引く 1) を 2 で割った乗が、n を法とする a のヤコビ記号に合同であることを意味します。a を割らない奇素数はすべて同じ合同を満たすため、なお通過する合成数は Solovay–Strassen 型検査の興味深い失敗例です。本チェッカーはその問いそのもののためにあります。奇合成数 n と底 a を受け取り、n がその底に対するオイラー・ヤコビ偽素数かを決めます。定義は奇合成数にしか適用されないためです。応答は gcd、ヤコビ記号、モジュラ冪、合同の成否、そして定義がすべて満たされたときだけ真となる真偽値を返します。
オイラー・ヤコビ偽素数とは何か、フェルマー判定およびオイラー判定との違い
オイラーの判定条件は、p が奇素数で a が p で割り切れないとき、a の (p 引く 1) を 2 で割った乗が、p を法とする a のルジャンドル記号に合同であると述べます。ヤコビ記号 (a/n) はその二次指標を奇素数から任意の正の奇数 n へ広げるため、p の代わりに n を置いた同じ合同を書きたくなります。
n が奇素数のとき両記号は一致し、合同は定理です。n が奇数かつ合成数のとき、n が素数でなくても一部の底では合同がなお成り立つことがあります。gcd(a, n) が 1 である限り、そのような n を底 a に対するオイラー・ヤコビ偽素数と呼びます。
この条件はフェルマー判定（a の n 引く 1 乗が n を法として 1 に合同）より厳密に強く、モジュラ冪がプラス 1 かマイナス 1 であることだけを求める弱いオイラー判定よりも強いです。典型例は底 2 に対する 341 です。
フェルマー偽素数であり、2 の 170 乗は 341 を法として 1 ですが、ヤコビ記号 (2/341) は −1 なのでオイラー・ヤコビ合同は失敗します。最小のカーマイケル数 561 は底 2 で合同を満たし、したがってその底に対するオイラー・ヤコビ偽素数です。底 10 の 91 も本チェッカーが確認する教室の定番例です。
本機能は合成数を素数と呼ばず、素数を偽素数とも呼びません。
入力するものと結果の読み方
そうすれば n の素数性は、その上界で決定的な固定証人の Miller–Rabin 集合で決まります。n が 9 未満、偶数、または素数の場合、ハンドラは要求を拒否します。オイラー・ヤコビ偽素数は定義上奇合成数であり、素数を失敗した偽素数として扱うと誤った教訓になるためです。
これらの検証失敗は課金されません。criterion 文字列は a^((n-1)/2) ≡ (a/n) (mod n) を再掲し、ページやノートが判定の横に定義を示せるようにします。gcd が 1 より大きいときヤコビは 0 であり、偶発的な冪が消えても対はオイラー・ヤコビ対ではありません。
例: n が 561 で a が 2 なら jacobi は 1、remainder は 1、旗は真。n が 341 で a が 2 なら jacobi は −1、remainder は 1、旗は偽です。算術はすべて厳密な BigInt であり、浮動小数点も乱択証人もありません。
オイラー・ヤコビ偽素数チェッカーが役立つ場面
整数論の授業やコンテスト用プラットフォームは、学習者がヤコビの相互法則とモジュラ冪を手実装せずにフェルマーの嘘つきと Solovay–Strassen の嘘つきを分けられるよう、オイラー・ヤコビ偽素数チェッカーを使います。研究ノートや趣味の走査は、公開リストの独立した神託が欲しいときに同じ契約を呼びます。
561、1105、1729 など底 2 の古典例はすべて真を返し、底 2 の 341 は偽を返さねばなりません。Solovay–Strassen 素数判定を紹介する暗号の演習では、素数の n を拒否する道具が必要です。教育上の要点はオイラーの判定をまねる合成数であり、素数が通ることを繰り返すことではないからです。
自前のヤコビやモジュラ冪ライブラリの性質テストを書く工学チームは、この応答を対照として固定できます。与えられた奇合成数が与えられた底でオイラー・ヤコビ合同を満たすかどうかだけが問のときに本ツールを選び、全底の探索、フェルマーだけの検査、Miller–Rabin 証人報告、数千ビット整数の証明書が必要なときには使わないでください。
活用例
Solovay–Strassen の嘘つきを教室で確認する
学習者に n を 561、底を 2 として送らせ、オイラー・ヤコビの旗が真であることを確認し、フェルマーの嘘つきにすぎない底 2 の 341 と対比してください。
公開表に対する独立した神託
オフラインのオイラー・ヤコビ偽素数リストを、決定的なヤコビ記号とモジュラ冪の実装で検証します。
整数論ライブラリの性質テスト
局所的な相互法則ルーチンが定義からずれないよう、単体テストで gcd、ヤコビ記号、remainder、真偽値を固定します。
よくある質問
n が底 a のオイラー・ヤコビ偽素数になる条件は何ですか？
n は奇数かつ合成数であり、gcd(a, n) は 1 で、a^((n−1)/2) は n を法としてヤコビ記号 (a/n) に合同でなければなりません。
偶数の n と素数の n が拒否されるのはなぜですか？
オイラー・ヤコビ偽素数は、オイラーの判定をまねる奇合成数として定義されます。
フェルマー偽素数と何が違いますか？
底 a のフェルマー偽素数は a^{n−1} ≡ 1 (mod n) だけで足ります。オイラー・ヤコビ検査は、そのフェルマー条件のモジュラ平方根がヤコビ記号と一致することまで求めます。341 は底 2 のフェルマーの嘘つきですが、底 2 のオイラー・ヤコビ偽素数ではありません。
561は底2のオイラー・ヤコビ偽素数ですか？
はい。2の280乗を561で割った余りは1で、2の561に対するヤコビ記号も1なので、561は合成数なのに合同式が成り立ちます。最小のカーマイケル数でもあります。
底と数に共通の因数がある場合はどうなりますか？
その底ではオイラー・ヤコビ偽素数になりません。定義では両者が互いに素である必要があるからです。答えは「いいえ」で、理由が分かるよう共通の約数も表示します。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/numth/euler-pseudoprime-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":561,"a":2}'const res = await fetch("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 561,
"a": 2
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/euler-pseudoprime-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 561,
"a": 2
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/euler-pseudoprime-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":561,"a":2}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":561,"a":2}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/euler-pseudoprime-check", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"n": 561,
"a": 2
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.euler_pseudoprime_check",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
制限
max_abs | 9007199254740991 |
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
偶数の n や素数の n は紛らわしい偽陰性ではなく invalid_input で拒否されます。同じ決定的モジュールがブラウザでは無料、API 経路では成功 1 回あたり $0.002 で動きます。
オイラー・ヤコビ偽素数とは何か、フェルマー判定およびオイラー判定との違い
素数や偶数の入力はエラーであり、真偽値 is_euler_jacobi_pseudoprime は n が受理された奇合成数で、対が互いに素で、ヤコビ合同が完全に成り立つときだけ真です。
入力契約、応答フィールド、エラー時の扱い
必須の整数を 2 つ含む JSON 本体を POST してください。奇合成の候補 n（別名 modulus と number）と底 a（別名 base）です。各フィールドは JSON 数値でも十進数字列でもよく、絶対値が JavaScript の安全整数範囲内の整数でなければなりません。欠落フィールド、分数、真偽値、空文字、過大な値はフィールド名を添えて invalid_input になります。成功時の本体は n と a を数値として返し、gcd と真偽値 coprime を報告し、jacobi を −1・0・1 のいずれかで返し、exponent を (n 引く 1) 割る 2、remainder をその指数による a の n を法とする余りとし、remainder が n を法とする剰余系へ還元したヤコビ記号と一致するとき congruence_holds を立て、対が互いに素で合同が成り立つときだけ is_euler_jacobi_pseudoprime を立てます。
オイラー・ヤコビ偽素数チェッカーが役立つ場面
本機能は純粋な parse の tier A なので、成功した呼び出しはすべて決定的でオフライン、モデルトークンなしの $0.002 です。n は奇数かつ合成数のままにし、invalid_input はクライアント側の修正として扱い、将来のリファクタがモジュラ結果を黙って変えないよう remainder と jacobi をテストに固定してください。
技術的な質問
gcd(a, n) が 1 より大きい場合はどうなりますか。
その対はオイラー・ヤコビ対ではありません。応答はなお gcd、jacobi 0、モジュラ剰余を返しますが、定義が互いに素であることを要求するため is_euler_jacobi_pseudoprime は偽です。
オイラー・ヤコビ偽素数チェッカーの料金はいくらですか。
ブラウザ上の道具は無料です。API 要求は成功 1 回あたり $0.002 で前払いの KIT 残高を使い、不正な入力は課金されません。