Modular nth root calculator
Find every k-th root of a number modulo a prime: the square roots of 2 modulo 17 are 6 and 11, listed in order. When no root exists you get a clear answer instead of an empty list. 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)
- 17
- A mod
- 2
- Root count
- 2
- Roots
- 6, 11
- Gcd k phi
- 2
A modular k-th root of an integer a modulo a prime p is any residue x such that x raised to the power k is congruent to a modulo p. Square roots modulo primes appear in Tonelli–Shanks tutorials, cubic and higher roots show up in finite-field algebra, and cryptography courses need a trustworthy oracle that either lists every root or refuses cleanly when none exist. This calculator accepts a, a positive exponent k, and a prime modulus p, reduces a into the canonical range zero through p minus one, and returns the complete ordered list of solutions in that field.
What modular k-th roots are and when they exist
In the multiplicative group of a prime field every nonzero residue has a well-defined order dividing p minus one. Raising x to the k produces a map whose image is the set of k-th power residues. For a nonzero target a the congruence x to the k congruent to a modulo p has solutions if and only if a raised to (p minus one) divided by d is congruent to one, where d is the greatest common divisor of k and p minus one.
When that criterion holds there are exactly d distinct nonzero roots. The zero residue is special: zero to any positive power is zero, so a congruent to zero has the single root zero. Composite moduli fall outside this clean cyclic-group picture and are rejected so the solver never pretends a Chinese-remainder product of local roots is a single prime-field answer.
Students meet square roots when they check Legendre symbols by hand, meet higher roots when they study cyclotomic cosets or discrete logarithms, and meet existence failures when a homework problem asks for a cube root of a non-cubic residue.
How this calculator finds every root
Call the capability with integer fields a, k, and p. The implementation first checks that k is a positive integer and that p is a prime within the published bound using a deterministic Miller–Rabin test. After reducing a modulo p, the zero-residue case returns the single root zero.
For nonzero a it computes d equals gcd of k and p minus one and applies the existence test above. When d equals one there is a unique root obtained by raising a to the modular inverse of k modulo p minus one, which is the fast path used for coprime exponents.
When d is greater than one the solver finds a primitive root g modulo p, recovers the discrete logarithm of a base g with baby-step giant-step, and solves the linear congruence k times y congruent to that logarithm modulo p minus one. Every returned root is verified by modular exponentiation before the response is emitted.
What you can do with it
Cryptography and finite-field labs
Instructors and students can list every square or higher root modulo a small prime, verify existence criteria, and inspect gcd(k, p−1) when a sample residue has no k-th root.
Contest programming and modular algebra
Competitive programmers can check x^k ≡ a (mod p) solutions against a deterministic oracle instead of hand-rolled Tonelli–Shanks or brute-force loops.
FAQ
What if no k-th root exists?
An empty success list is never returned for non-existence.
Which algorithms does the modular nth root calculator use?
Miller–Rabin for primality, modular inverse exponents when gcd(k,p−1)=1, otherwise a primitive root, baby-step giant-step discrete log, and linear congruence solving. All paths are deterministic.
Is the modular nth root calculator free?
The browser tool runs free on your device.
What are the square roots of 2 modulo 17?
They are 6 and 11. Squaring either one and dividing by 17 leaves the remainder 2. The calculator lists both in ascending order, together with the count of roots.
How many roots can there be?
When roots exist there are exactly as many as the greatest common divisor of k and p − 1, so two square roots of 2 modulo 17. Zero has the single root zero, and requests with more than ten thousand roots are refused.
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/modular-nth-root \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"k":2,"p":17}'const res = await fetch("https://api.kit.forhosting.com/numth/modular-nth-root", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"k": 2,
"p": 17
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/modular-nth-root",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"k": 2,
"p": 17
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/modular-nth-root", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"k":2,"p":17}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"k":2,"p":17}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/modular-nth-root", 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": 2,
"p": 17
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.modular_nth_root",
"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
When p is composite the request fails with invalid_input; when the existence criterion a to the power (p minus one) over gcd of k and p minus one is not one modulo p, the request likewise fails instead of returning an empty success list. The same pure deterministic module powers the free browser tool and the prepaid API path, so classroom demos and automated graders never disagree on a root.
What modular k-th roots are and when they exist
Returning a hard invalid_input on non-existence matches the language of number-theory texts that say no solution rather than an empty list that billing systems might treat as success.
How this calculator finds every root
Each solution y yields a root g to the y, and the distinct roots are sorted ascending for a stable API contract. Absolute values of a and k are bounded by one trillion and the prime p is capped near one billion so baby-step giant-step memory stays practical; if d would exceed ten thousand roots the request is refused rather than flooding the client.
Practical use, limits, pricing, and delivery
Use the browser tool when you want every square root or higher root while reading a crypto note, checking contest-programming output, or grading a finite-field homework set. Accepted inputs are integers a with absolute value at most one trillion, exponents k from one through one trillion, and primes p from two through about one billion, subject to the root-count safety cap. Use the API when a script, LMS plugin, or research notebook needs many modular root queries without embedding Tonelli–Shanks or a discrete-log routine. Each successful request is one billable item at $0.002; validation failures, composite moduli, and proven non-existence do not consume balance. The response echoes a, k, p, the reduced a_mod, root_count, the ascending roots array, gcd_k_phi equal to d, a display equation string, and a short method tag naming which algorithm path ran. Wire the endpoint into cryptography teaching sandboxes, competitive-programming helpers, and algebraic number-theory demos that already prefer exact modular arithmetic over floating approximations. Because the unit is a single item and the engine is pure parse, latency stays low and the free web channel mirrors the paid API without a second code path that could drift.
Integration use cases
Homework checkers and research notebooks
Automated graders and scripts can confirm root sets, reject composite moduli via invalid_input, and keep every intermediate product inside documented integer bounds.
Technical questions
How do I compute modular k-th roots with this API?
Send JSON with integer fields a, k (≥ 1), and prime p to numth.modular_nth_root. On success the response returns roots as an ascending array, root_count, a_mod, and gcd_k_phi.
What happens if p is not prime?
The request fails with invalid_input. This calculator requires a prime modulus so the multiplicative group is cyclic and the existence criterion is exact. Failed validation is not charged.