Nth power residue checker
Tells you whether a number is a k-th power modulo a prime: 2 is a square modulo 7, because 2 raised to the power 3 leaves remainder 1. It handles squares, cubes and any higher power with exact whole numbers. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- A
- 2
- K
- 2
- Power (W)
- 7
- A mod
- 2
- Gcd
- 2
- Group order
- 6
- Criterion exp
- 3
An integer a is a k-th power residue modulo a prime p when some integer x satisfies x to the k congruent to a modulo p. That question generalizes quadratic residuosity (the k equals two case) to cubes, higher powers, and arbitrary positive exponents used in contest number theory and introductory cryptography. This capability takes a candidate a, a positive exponent k, and a prime modulus p, reduces a into the range zero through p minus one, verifies that p is prime, and applies the standard cyclic-group criterion on the multiplicative group of the field with p elements. When a is divisible by p the answer is always yes for k at least one, because zero to any positive power is zero.
What a k-th power residue means modulo a prime
Fix a prime modulus p and a positive integer k. The residue classes modulo p form a field, and its nonzero elements form a cyclic multiplicative group of order p minus one. An integer a not divisible by p is a k-th power residue modulo p precisely when a lies in the image of the map that sends each nonzero class x to x raised to the k.
Because the group is cyclic, that image is the unique subgroup of index equal to the greatest common divisor d of k and p minus one, and a belongs to that subgroup if and only if a raised to the power (p minus one) divided by d is congruent to one modulo p. That single modular exponentiation is the decision procedure used here.
When a is divisible by p, the congruence x to the k congruent to a has the trivial solution x congruent to zero for every k at least one, so zero is always treated as a k-th power residue. Special cases recover familiar tools: for k equals two and odd prime p the criterion is Euler’s criterion for quadratic residuosity, the same information carried by the Legendre symbol, while for k equal to p minus one every nonzero a is a residue by Fermat’s little theorem.
Send integers a, k, and p. The exponent k must be at least one and at most one trillion. Optional field names are never filled with null: the criterion pair is simply omitted for the zero-residue case.
Classic checks you can reproduce by hand: for a equals two, k equals three, and p equals seven, gcd of three and six is three so the criterion exponent is two and two squared is four modulo seven, not one, therefore two is not a cubic residue modulo seven; by contrast one is always a k-th power residue for every prime because one to any power is one. Non-integers, missing required fields, and exponents below one fail validation with a clear English message.
Where higher-power residue checks show up in real work
Contest programmers need a fast oracle before attempting to extract modular cube roots or higher roots: if the residue bit is false there is no point searching for x. Cryptography students verify exercises about the image of the power map in finite fields, index-calculus examples, and toy constructions that depend on whether a message class is a k-th power before applying a map. Research and homework pipelines that already use Legendre or Jacobi symbols for squares often need the same yes-or-no answer for cubes and higher powers without switching libraries.
If you only need quadratic residuosity, the dedicated quadratic residue and Legendre symbol tools remain available; this landing is the general k-th power decision for prime moduli.
What you can do with it
Homework and contest checks
Decide whether a is a k-th power modulo prime p for number-theory exercises without writing your own modular exponentiation and gcd pipeline.
Pre-filter before root extraction
Reject non-residues early in a pipeline that would otherwise attempt modular cube-root or higher-root algorithms over a prime field.
Teaching the cyclic-group criterion
Show students gcd(k, p−1), the criterion exponent, and the modular power that proves or disproves residuosity for concrete triples.
FAQ
What is a k-th power residue modulo a prime p?
An integer a is a k-th power residue modulo prime p if there exists an integer x such that x^k ≡ a (mod p). This tool reports that fact using the cyclic-group criterion on F_p*.
Why must p be prime?
The decision procedure used here relies on the multiplicative group modulo p being cyclic of order p−1, which holds for prime moduli.
How is the yes-or-no answer computed?
Let d = gcd(k, p−1). If a is not divisible by p, a is a k-th power residue iff a^((p−1)/d) ≡ 1 (mod p).
What does it cost?
The browser tool is free and runs locally.
Is 2 a cubic residue modulo 7?
No. The greatest common divisor of 3 and 6 is 3, so the test raises 2 to the power 2, which gives 4 modulo 7 instead of 1. That means no whole number cubed leaves remainder 2.
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/power-residue-check \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"k":3,"p":7}'const res = await fetch("https://api.kit.forhosting.com/numth/power-residue-check", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"k": 3,
"p": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/power-residue-check",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"k": 3,
"p": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/power-residue-check", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"k":3,"p":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"k":3,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/power-residue-check", 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,
"k": 3,
"p": 7
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.power_residue_check",
"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.
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
What a k-th power residue means modulo a prime
The endpoint does not invent floating-point roots or approximate powers; it only uses exact integer modular arithmetic so that textbook answers and automated tests agree bit for bit.
Input contract, prime check, and response fields
The modulus p must be a prime between two and one trillion inclusive; composite values such as nine or fifteen are rejected with invalid_input and a message that names the field and states that p is not prime, so those calls are not charged. The candidate a may be negative or larger than p in absolute value up to the same trillion bound; it is reduced to a_mod in the half-open interval from zero inclusive to p exclusive before the test. On success the payload always includes a, k, p, a_mod, the boolean is_power_residue, the gcd of k and p minus one, the group_order equal to p minus one, and a short English interpretation string. When a_mod is nonzero the payload also reports criterion_exp equal to (p minus one) divided by that gcd and criterion_value equal to a_mod raised to that exponent modulo p, which equals one exactly when the residue bit is true. The same pure function powers the free browser tool and the paid API path.
Where higher-power residue checks show up in real work
Teachers assign problems such as decide whether three is a fifth-power residue modulo eleven or list which residue classes are cubes modulo thirteen and want a deterministic JSON answer rather than a handwritten table that may miss a class. Because the capability is a pure parse engine there is no model drift, no external API key, and no stored state: the same triple always yields the same boolean and the same criterion value. API pricing is the published base of $0.002 per successful item; failed validation does not consume balance.
Technical questions
Is 0 considered a k-th power residue?
Yes. For every k ≥ 1 we have 0^k ≡ 0 (mod p), so a_mod = 0 is always a power residue and the criterion exponent fields are omitted.