Count primitive roots modulo n
Modulo 18 there are exactly 2 primitive roots, the value of Euler's totient applied twice. Enter a modulus and see how many generators it has, or a clear notice when it has none, as happens with 8. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 18
- Modulus
- 18
- Primitive root count
- 2
This primitive-root counter determines whether a modulus supports primitive roots and, when it does, returns their exact number. The result is the Euler totient of the modulus's Euler totient, written phi(phi(n)). The calculator handles the complete family of eligible moduli rather than assuming that the input is prime. If the modulus belongs to a class with no primitive roots, it reports a clear input error instead of returning a misleading zero.
What the count means
A primitive root modulo n is a residue whose repeated powers generate every invertible residue class modulo n. In group language, it is a generator of the multiplicative group of integers modulo n. This tool answers a precise question: how many distinct residue classes are generators of that group?
It does not list the generators or search for the smallest one. When a primitive root exists, the multiplicative group is cyclic and has phi(n) elements. A cyclic group of order phi(n) has exactly phi(phi(n)) generators, which is the value returned here.
For example, modulo 18 the invertible residues form a cyclic group of order 6, and phi(6) is 2, so there are two primitive roots. The count concerns residue classes modulo n, not arbitrary integer representatives: values that differ by a multiple of n describe the same root. This distinction makes the result useful in proofs, exercises, and algorithms where the size of the generator set matters more than the identities of its members.
Which moduli have primitive roots
Primitive roots do not exist for every positive modulus. The complete classification says they exist only when n is 2, 4, an odd prime power p^k, or twice an odd prime power 2p^k. The calculator factors the supplied modulus and applies that theorem before computing a count.
This is important because blindly evaluating phi(phi(n)) for an ineligible modulus produces a positive number even though there are no generators. For instance, phi(8) is 4 and phi(4) is 2, but no primitive root exists modulo 8; returning 2 would therefore be mathematically wrong. This capability rejects such a modulus with an explicit error.
Prime moduli greater than two are included as the special case p^1, while composite examples such as 9, 14, 18, and 25 also qualify. Moduli such as 8, 12, 15, and 20 do not. The classification check and the counting formula are kept separate so the output always represents an actual set of primitive roots rather than an unqualified totient calculation.
How to use and interpret the result
Submit one integer n between 2 and 1,000,000,000,000. Inputs must be numeric integers, not decimal strings, fractions, scientific approximations, negative values, or unsafe JavaScript integers. The upper bound keeps factorization work finite and predictable while covering a broad range of classroom and practical calculations.
Internally, the algorithm uses deterministic trial division to obtain the prime-power structure, applies the existence theorem, computes phi(n) from the distinct prime factors, and then computes phi(phi(n)). It makes no network request and uses no random search, so identical inputs always produce identical outputs.
What you can do with it
Check a number theory exercise
Verify the expected number of generators before enumerating primitive roots by hand.
Size a generator search
Determine how many successful residue classes an exhaustive primitive-root search should find.
Validate an eligible modulus
Reject a modulus whose multiplicative group is not cyclic before a later algorithm assumes a primitive root exists.
FAQ
What formula does the calculator use?
For a modulus that admits primitive roots, it returns phi(phi(n)), where phi is Euler's totient function.
Why does the tool return an error instead of zero?
The capability contract distinguishes an unsupported mathematical case from a valid count. A modulus without primitive roots is therefore reported as invalid input.
Which moduli admit primitive roots?
Exactly 2, 4, odd prime powers p^k, and twice odd prime powers 2p^k.
Does this list the primitive roots?
No. It returns only how many primitive-root residue classes exist modulo n.
Are prime moduli supported?
Yes. Every prime modulus has primitive roots, including 2; odd primes are instances of the odd prime-power case.
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/count-primitive-roots \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":18}'const res = await fetch("https://api.kit.forhosting.com/numth/count-primitive-roots", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 18
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/count-primitive-roots",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 18
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/count-primitive-roots", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":18}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":18}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/count-primitive-roots", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": 18
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.count_primitive_roots",
"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
How to use and interpret the result
The response repeats it as modulus and provides primitive_root_count as an exact integer. Treat an invalid_input response saying that no primitive roots exist as a mathematical conclusion about the modulus, not as a transient service failure. If you need the roots themselves, use a generator-finding or enumeration tool instead; this endpoint deliberately returns only the cardinality. API requests cost $0.002, with the same exact arithmetic used for every accepted input.
Technical questions
What does an API request cost?
Each API request costs $0.002.