Quadratic residue checker
Tells you whether a number has a square root modulo m, and lists every root: 2 is a square modulo 7, because 3 squared is 9, which leaves 2, and the roots are 3 and 4. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- A
- 2
- Modulus m
- 7
- A mod
- 2
- Roots
- 3, 4
- Root count
- 2
An integer a is a quadratic residue modulo m when some integer x satisfies x squared congruent to a modulo m — in other words, a has a modular square root. That yes-or-no question appears in cryptography homework, contest number theory, and any workflow that needs to know whether a congruence is a perfect square before spending effort on a larger solver. This capability takes a and a modulus m (at least two), reduces a into the canonical range zero through m minus one, scans for every root in that range, and can optionally return the complete list of quadratic residue classes modulo m.
What quadratic residuosity means for general moduli
In elementary number theory a quadratic residue modulo a prime p usually means an integer a not divisible by p for which the congruence x squared equals a modulo p has a solution; zero is often discussed separately as the trivial square. For a composite modulus m the same definition extends cleanly: a is a quadratic residue modulo m when there exists at least one integer x with x squared congruent to a modulo m, including the case a congruent to zero.
Solutions come in patterns that depend on the prime-power factorization of m; for example modulo a prime there are either zero or two nonzero roots for each nonzero residue class that is a square, while composite moduli can admit more roots. Classic tools such as the Legendre and Jacobi symbols give fast tests when m is an odd prime or when you only need a multiplicative character, but they do not by themselves list every root for arbitrary m.
A direct scan of x from zero through m minus one evaluates every square class exactly once and therefore answers both existence and enumeration for any modulus inside a fixed size bound.
Where modular square checks show up in real work
Contest programmers often need a quick oracle before invoking Tonelli–Shanks or a CRT combination of prime-power roots: if the residue bit is false, there is no point constructing a square root. Cryptography students verify examples for Rabin-style ciphers, quadratic reciprocity exercises, and toy Diffie–Hellman variants that mention residue symbols. Engineers reconciling periodic schedules or hash-bucket experiments sometimes ask whether a stride is a square class modulo a composite period.
If you only need Legendre-symbol style yes-or-no for a large prime beyond the scan limit, factor or reduce first; within the cap this landing is the complete constructive answer.
What you can do with it
Homework and contest checks
Decide whether a is a square modulo m and read every root in 0..m-1 for number-theory exercises without building a full CRT solver.
Pre-filter before root extraction
Reject non-residues early in a pipeline that would otherwise attempt modular square-root algorithms on composite or prime moduli.
FAQ
What is a quadratic residue modulo m?
An integer a is a quadratic residue modulo m if there exists an integer x such that x² ≡ a (mod m). This tool reports that fact and lists every such x in 0..m-1.
Why must m be at least 2?
Modulus 0 is undefined for congruences in this product surface, and modulus 1 collapses every integer to a single class.
What modulus size is supported?
m must be an integer from 2 through 1,000,000 inclusive. The candidate a may be any safe integer; it is reduced modulo m before the scan.
What does it cost?
The browser tool is free and runs locally.
Is 3 a quadratic residue modulo 7?
No. Squaring every remainder modulo 7 only ever gives 0, 1, 2 or 4, so no whole number squared leaves 3, and the list of roots comes back empty.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
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)Example request
{
"a": 2,
"m": 7
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.quadratic_residue",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
min_m | 2 |
max_m | 1000000 |
max_abs_a | 9007199254740991 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
Input contract, limits, and response fields
Send integers a and m. Typical classroom checks: two is a quadratic residue modulo seven because three squared is nine which is two mod seven, and the roots are three and four; three is not a quadratic residue modulo seven. Non-integers, empty required fields, and moduli above the cap fail validation with a clear English message naming the field. The modulus m must be at least two and at most one million; values below two are rejected with invalid_input and are not charged, because modular arithmetic with modulus zero or one is not a supported product surface. The candidate a may be negative or larger than m; it is reduced to a_mod in the half-open interval from zero inclusive to m exclusive before the square search. Optional boolean list_residues (aliases list_all and all_residues) asks for every distinct value of x squared modulo m, sorted ascending, together with residue_count. On success the payload always includes a, m, a_mod, is_quadratic_residue, roots as the full list of solutions in zero through m minus one, and root_count. When list_residues is true for m equals seven you obtain the sorted classes zero, one, two, and four — the image of the squaring map on the ring of integers modulo seven.
Where modular square checks show up in real work
Teachers assign problems such as list all quadratic residues modulo twenty-one or decide whether five is a square modulo thirteen and want a deterministic JSON answer rather than a handwritten table that may contain off-by-one mistakes. Because the capability is a pure parse engine there is no model drift, no external API key, and no stored state: the same pair always yields the same roots and the same optional residue list. API pricing is the published base of $0.002 per successful item; failed validation does not consume balance.
Integration use cases
Enumerate residue classes
Set list_residues true to obtain the sorted image of the squaring map modulo m for tables, teaching slides, or property-based tests.
Technical questions
Is 0 considered a quadratic residue?
Yes. 0² ≡ 0 (mod m), so a_mod = 0 is always a residue and includes root 0 (and possibly others for composite m).