ForHosting KIT · 数学

平方剰余チェッカー

ある数が法mで平方根を持つかを判定し、根をすべて一覧にします。2は法7で平方剰余です。3の2乗は9で余りが2になり、根は3と4です。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

A: 2
法 m: 7

結果

A の剰余: 2
根: 3, 4
根の個数: 2

整数 a が法 m の平方剰余であるとは、ある整数 x が x の二乗 ≡ a (mod m) を満たすこと、すなわち a がモジュラー平方根を持つことです。この yes/no の問いは暗号の宿題、競技数論、より大きなソルバーに手を出す前に合同が完全平方かどうかを知る必要があるあらゆる流れに現れます。本能力は a と法 m（2 以上）を受け取り、a を 0 から m−1 の標準範囲に約し、その範囲のすべての根を走査し、任意で法 m の平方剰余類の完全リストも返せます。

一般の法における平方剰余性の意味

初等数論では素数 p を法とする平方剰余は通常、p で割り切れない整数 a で合同 x² ≡ a (mod p) が解を持つものを指し、0 は自明な平方として別扱いされることが多いです。合成数 m では同じ定義が素直に拡張されます。

a が法 m の平方剰余であるとは、x² ≡ a (mod m) を満たす整数 x が少なくとも一つ存在することであり、a ≡ 0 の場合も含みます。解のパターンは m の素冪分解に依存します。例えば素数法では平方である各非零剰余類に対し非零根は 0 個または 2 個ですが、合成法ではより多くの根があり得ます。

Legendre 記号や Jacobi 記号のような古典的道具は m が奇素数のときや乗法的指標だけが必要なときに高速判定を与えますが、任意の m のすべての根を単独では列挙しません。x を 0 から m−1 まで直接走査すると各平方類をちょうど一度評価し、固定サイズ上限内の任意の法について存在と列挙の両方に答えます。

実務でモジュラー平方チェックが現れる場面

競技プログラマーは Tonelli–Shanks や素冪根の CRT 結合の前にしばしば素早いオラクルを要します。剰余ビットが偽なら平方根を構成する意味がありません。暗号の学生は Rabin 風暗号、平方剰余相互法則の演習、剰余記号に触れる玩具 Diffie–Hellman の例を検証します。

周期スケジュールやハッシュバケツ実験を突き合わせる技術者は、ある歩幅が合成周期を法とする平方類かどうか問うことがあります。検証失敗は残高を消費しません。走査限界を超える大素数で Legendre 記号風の yes/no だけなら、まず因数分解または縮小してください。

上限内ではこのページが完全な構成的答えです。

活用例

宿題・競技の検算

a が法 m の平方かを判定し、CRT ソルバーを組まずに 0..m-1 の全根を数論演習で読み取れます。

根の抽出前の事前フィルタ

合成法や素数法でモジュラー平方根アルゴリズムを試す前に、非剰余をパイプラインの早い段階で棄却します。

よくある質問

法 m の平方剰余とは何ですか？

整数 a が法 m の平方剰余であるとは、x² ≡ a (mod m) を満たす整数 x が存在することです。本ツールはその事実を報告し、0..m-1 のすべてのそのような x を列挙します。

なぜ m は 2 以上でなければならないのですか？

法 0 はこの製品面の合同では未定義であり、法 1 はすべての整数を単一の類に潰します。

対応する法の大きさは？

m は 2 から 1,000,000 までの整数である必要があります。候補 a は安全な任意の整数でよく、走査前に m を法として約されます。

3は法7の平方剰余ですか？

いいえ。法7で各余りを2乗しても0、1、2、4しか現れないため、2乗して余り3になる整数はなく、根の一覧は空になります。

法mのすべての平方を一度に見られますか？

はい。一覧表示の項目を選ぶと、平方として現れる余りが小さい順に個数とともに表示されます。法7なら0、1、2、4です。

開発者向け — APIアクセス

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

エンドポイント

POSThttps://api.kit.forhosting.com/numth/quadratic-residue

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

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/numth/quadratic-residue \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"a":2,"m":7}'

const res = await fetch("https://api.kit.forhosting.com/numth/quadratic-residue", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "a": 2,
    "m": 7
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/quadratic-residue",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "a": 2,
    "m": 7
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/quadratic-residue", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"a":2,"m":7}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"a":2,"m":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/quadratic-residue", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "a": 2,
  "m": 7
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.quadratic_residue",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

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

料金

1リクエストあたり$0.002

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

制限

`min_m`	2
`max_m`	1000000
`max_abs_a`	9007199254740991

エラー

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

技術的な注記

一般の法における平方剰余性の意味

本エンドポイントが実装するのはその網羅的手法です。決定的な整数演算のみ、浮動小数の丸めなし、テストで断言できる安定した JSON 形。

入力契約、制限、応答フィールド

整数 a と m を送ってください。法 m は 2 以上 100 万以下である必要があります。法 0 や 1 のモジュラー演算はサポートする製品面ではないためです。典型的な授業チェック: 2 は法 7 の平方剰余です。3²=9≡2 (mod 7) で根は 3 と 4。3 は法 7 の平方剰余ではありません。2 未満は invalid_input で拒否され課金されません。候補 a は負でも m より大きくてもよく、平方探索の前に a_mod として 0 以上 m 未満の半開区間に約されます。任意の真偽値 list_residues（エイリアス list_all, all_residues）は x² mod m の相異なる値を昇順で、residue_count と共に要求します。成功時のペイロードは常に a, m, a_mod, is_quadratic_residue、0 から m−1 の全解リスト roots、root_count を含みます。m=7 で list_residues が真のとき、昇順クラス 0,1,2,4 — 整数環 modulo 7 上の平方写像の像 — が得られます。非整数、空の必須フィールド、上限超の法はフィールド名を示す明確なメッセージで検証失敗します。同じ純関数が無料ブラウザツールと有料 API 経路を駆動するため、宿題確認と CI フィクスチャが静かに食い違うことはありません。

実務でモジュラー平方チェックが現れる場面

教員は法 21 の平方剰余をすべて列挙する、5 が法 13 の平方か判定するなどの問題を出し、オフバイワンを含み得る手書き表ではなく決定的 JSON を望みます。本能力は純 parse エンジンなのでモデル揺らぎもなく外部 API キーもなく保存状態もなく、同じ対は常に同じ根と同じ任意剰余リストを返します。API 料金は成功 1 件あたり公開ベース $0.002 です。

連携の活用例

剰余類の列挙

list_residues を真にして、表・教材スライド・プロパティベーステスト向けに法 m の平方写像の昇順像を得ます。

技術的な質問

0 は平方剰余とみなされますか？

はい。0² ≡ 0 (mod m) なので a_mod = 0 は常に剰余であり、根 0 を含みます（合成 m では他の根もあり得ます）。

料金はいくらですか？

ブラウザツールは無料でローカル実行です。API は前払い KIT 残高を成功 1 件あたり $0.002 で使用し、無効入力は課金されません。

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

平方剰余チェッカー

無料で実行

計算例

一般の法における平方剰余性の意味

実務でモジュラー平方チェックが現れる場面

活用例

宿題・競技の検算

根の抽出前の事前フィルタ

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

制限

エラー

技術的な注記

一般の法における平方剰余性の意味

入力契約、制限、応答フィールド

実務でモジュラー平方チェックが現れる場面

連携の活用例

剰余類の列挙

技術的な質問

ありがとう