Primitive root calculator
Finds the smallest primitive root of a prime: modulo 7 it is 3, whose powers run through all six nonzero remainders, while the powers of 2 repeat after three. You also see p − 1 split into prime powers. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- Power (W)
- 7
- Primitive root
- 3
- Order
- 6
- Max digits
- 15
A primitive root modulo a prime p is a generator of the multiplicative group of nonzero residues modulo p. In plain terms, some integer g between 1 and p minus one has the property that its successive powers g, g squared, g cubed, and so on, eventually hit every residue class coprime to p before repeating. That g is a generator of (Z/pZ)*, and the smallest such positive g is the classic number-theory answer students, cryptographers, and contest solvers look up. This calculator takes a prime modulus p, verifies that p is prime, factors p minus one, and returns the least primitive root together with the group order and the prime-power factorisation of p minus one. The path is fully deterministic: Miller–Rabin with fixed witness sets, trial factorisation, and modular exponentiation with no network, no randomness, and no date dependence.
What a primitive root is and what you get
For a prime modulus p the set of residues 1, 2, …, p minus one forms a cyclic multiplicative group of order p minus one. An integer g is a primitive root modulo p when the order of g in that group is exactly p minus one: the powers g to the k for k from 0 through p minus two are all distinct modulo p and exhaust every nonzero residue.
Not every integer is a generator; for example modulo 7 the powers of 2 cycle through only three values before repeating, so 2 is not a primitive root, while 3 generates all six units and is the smallest one. There is no probabilistic guess presented as a root and no silent fallback for composite moduli, because a primitive root in the classical sense is defined for primes (and a few special composite families this page does not cover).
If you need factors of an arbitrary integer rather than a generator mod p, use a factorisation capability instead; this page answers only the smallest-generator-mod-prime question.
How the prime is checked and how the smallest root is found
Optional leading plus signs are allowed; embedded spaces, hex prefixes, and exponential notation are rejected with a clear message so a bad cell does not become a wrong generator. After parsing, the engine runs a deterministic Miller–Rabin primality test with witness sets proven sufficient for every integer of at most fifteen decimal digits.
When p is prime, the engine factors p minus one by wheel trial division, collects the distinct prime factors q of that order, and searches g equals 2, 3, 4, … for the first candidate such that g raised to (p minus one) divided by q is not congruent to 1 modulo p for every such q. That classical criterion is necessary and sufficient for g to have order p minus one. The special case p equals 2 returns primitive root 1, the unique unit in that group.
Where smallest primitive roots fit in study, crypto, and code
Students meet primitive roots when learning cyclic groups, discrete logarithms, and the structure of finite fields of prime order. Worksheets often ask for the least generator modulo a small prime; this page returns that answer with the supporting factorisation of p minus one so you can verify the order tests by hand. Contest problems and programming-kata statements frequently require the smallest primitive root as a subroutine for constructing primitive polynomials, indexing discrete-log tables, or seeding number-theory demos.
Teachers can pre-generate answer keys without trusting opaque web widgets.
What you can do with it
Homework and contest preparation
Look up the smallest primitive root modulo a prime for textbook exercises, discrete-log drills, and programming contests that demand the least generator.
Teaching cyclic groups
Show that powers of the returned root exhaust (Z/pZ)* and contrast with non-generators using the factorisation of p−1 in the response.
FAQ
What does the primitive root calculator cost?
It is free in your browser on this page.
What if p is not prime?
Classical primitive roots in this sense are defined for prime moduli; composite n is out of scope.
Is the algorithm randomized?
No. Primality uses deterministic Miller–Rabin witness sets, factorisation is trial division, and modular powers are exact. The same p always yields the same root.
What is the largest prime I can send?
p may have at most 15 decimal digits. Larger values fail with a clear message that the digit limit was exceeded.
Why are the prime factors of p − 1 shown?
They are what the check uses. A candidate g is a primitive root when g raised to (p − 1) divided by q is not 1 modulo p for every prime q dividing p − 1, so the factors let you redo the test.
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/primitive-root \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"p":"7"}'const res = await fetch("https://api.kit.forhosting.com/numth/primitive-root", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"p": "7"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/primitive-root",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"p": "7"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/primitive-root", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"p":"7"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"p":"7"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/primitive-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
{
"p": "7"
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.primitive_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.
Limits
max_digits | 15 |
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 primitive root is and what the response contains
This tool returns the prime p as a decimal string, the smallest primitive root, the group order p minus one, a boolean is_prime flag that is always true on success, the ordered prime-power factors of p minus one used in the order tests, and the published max_digits limit so clients can validate before a batch. Failure modes are explicit: missing p, non-integers, fractions, scientific notation, values below two, values with more than fifteen digits, and composite p all raise invalid_input.
How the prime is checked and how the smallest root is found
The preferred field is p as a JSON integer or decimal string; aliases prime, modulus, and n are accepted so forms, query strings, and spreadsheets can reuse the same contract. If the test fails, the response is invalid_input naming that p is not prime.
Where smallest primitive roots fit in study, crypto, and code
On this page the work runs entirely in your browser; through the API each successful lookup costs $0.002, failed validation is not charged, and nothing is stored after the response returns. That split — free interactive exploration and a priced, identical API — matches the rest of the KIT tier-A catalog and lets you move from a classroom demo to an automated pipeline without changing the mathematical result.
Integration use cases
Deterministic crypto-parameter tests
Generate reproducible generators for unit tests of modular order, Diffie–Hellman demos on toy primes, and CI assertions without embedding static tables.
Technical questions
Is the result always the smallest primitive root?
Yes. The engine searches g = 2, 3, 4, … and returns the first generator, so the root is minimal among positive residues.