Primitive Root Calculator
Enter a modulus n to find its primitive roots (generators), see why they exist or not, and optionally check the multiplicative order of your own candidate g.
What is a primitive root?
For a modulus n, the integers coprime to n form a group under multiplication modulo n. It has φ(n) elements. A primitive root is an element g whose powers g, g², g³, … run through every one of those φ(n) elements before repeating. Equivalently, the multiplicative order of g, the smallest k with gk ≡ 1 (mod n), equals φ(n).
For n = 7, the number 3 is a primitive root: 3, 2, 6, 4, 5, 1 are its successive powers and they cover every non-zero residue. The number 2 is not, because 2³ ≡ 1 (mod 7) and its powers only produce 2, 4, 1.
When do primitive roots exist?
Gauss showed that primitive roots exist exactly when n is 1, 2, 4, an odd prime power pk, or twice an odd prime power 2pk. So there are primitive roots modulo 9, 10 and 25 but none modulo 8, 12 or 15. When a primitive root exists, there are exactly φ(φ(n)) of them. For a prime p that is φ(p − 1): modulo 13 there are φ(12) = 4 of them, namely 2, 6, 7 and 11.
How the test works
Checking every power of g would be slow for large n. Instead the calculator factors φ(n) and tests only the exponents φ(n)/q for each prime q dividing φ(n). The element g is a primitive root if and only if none of the values gφ(n)/q equals 1 modulo n. The tool displays this table for each candidate it tries, starting at g = 2, so the smallest primitive root is found and explained. All other primitive roots are the powers gk where gcd(k, φ(n)) = 1.
Why primitive roots matter in cryptography
The Diffie–Hellman key exchange and ElGamal encryption work in the group generated by an element g modulo a prime p. Using a primitive root (or an element of large prime order) means the powers of g cover as much of the group as possible, which makes the discrete logarithm problem hard. The textbook examples with p = 23 and g = 5 use the fact that 5 is a primitive root modulo 23.
Worked examples
These examples are computed by the same engine as the calculator above, so you can compare each step with your own working.
n = 23
- Modulus n:
23 - Check my own g (optional, 0 = skip):
0
Number of primitive roots
10
φ(φ(n)); all are listed in the solution
Step-by-step solution
Formula used
g is a primitive root mod n ⇔ ord_n(g) = φ(n)
Test: g^(φ(n)/q) ≢ 1 (mod n) for every prime q | φ(n)
Number of primitive roots (when any exist) = φ(φ(n))
CalculateFactor the modulus
23 = 23
CalculateDoes a primitive root exist?
Primitive roots exist exactly for n = 1, 2, 4, p^k, 2p^k (p an odd prime)
23 has the required form, so the group of units modulo 23 is cyclic.
CalculateCompute φ(n) and factor it
g is a primitive root ⇔ g^(φ/q) ≢ 1 (mod n) for every prime q dividing φ(n)
φ(23) = 22
φ(n) = 2 × 11
Primes q dividing φ(n): 2, 11
CalculateTest g = 2
A power equals 1, so 2 has smaller order and is not a primitive root.
| prime q | φ/q | g^(φ/q) mod 23 |
|---|
| 2 | 11 | 1 |
| 11 | 2 | 4 |
CalculateTest g = 3
A power equals 1, so 3 has smaller order and is not a primitive root.
| prime q | φ/q | g^(φ/q) mod 23 |
|---|
| 2 | 11 | 1 |
| 11 | 2 | 9 |
CalculateTest g = 4
A power equals 1, so 4 has smaller order and is not a primitive root.
| prime q | φ/q | g^(φ/q) mod 23 |
|---|
| 2 | 11 | 1 |
| 11 | 2 | 16 |
ResultTest g = 5
No power equals 1, so 5 is a primitive root.
| prime q | φ/q | g^(φ/q) mod 23 |
|---|
| 2 | 11 | 22 |
| 11 | 2 | 2 |
CalculateCount the primitive roots
count = φ(φ(n))
φ(22) = 10
ResultAll primitive roots
g^k with gcd(k, φ(n)) = 1
5, 7, 10, 11, 14, 15, 17, 19, 20, 21
CheckVerify by direct counting
Computing successive powers of 5 modulo 23 returns to 1 only after 22 steps = φ(n), so it generates every unit.
n = 13, test g = 2
- Modulus n:
13 - Check my own g (optional, 0 = skip):
2
Number of primitive roots
4
φ(φ(n)); all are listed in the solution
Order of 2
12
primitive root
Your g = 2 has multiplicative order 12 modulo 13, which equals φ(n): it IS a primitive root.
Step-by-step solution
Formula used
g is a primitive root mod n ⇔ ord_n(g) = φ(n)
Test: g^(φ(n)/q) ≢ 1 (mod n) for every prime q | φ(n)
Number of primitive roots (when any exist) = φ(φ(n))
CalculateFactor the modulus
13 = 13
CalculateDoes a primitive root exist?
Primitive roots exist exactly for n = 1, 2, 4, p^k, 2p^k (p an odd prime)
13 has the required form, so the group of units modulo 13 is cyclic.
CalculateCompute φ(n) and factor it
g is a primitive root ⇔ g^(φ/q) ≢ 1 (mod n) for every prime q dividing φ(n)
φ(13) = 12
φ(n) = 2^2 × 3
Primes q dividing φ(n): 2, 3
ResultTest g = 2
No power equals 1, so 2 is a primitive root.
| prime q | φ/q | g^(φ/q) mod 13 |
|---|
| 2 | 6 | 12 |
| 3 | 4 | 3 |
CalculateCount the primitive roots
count = φ(φ(n))
φ(12) = 4
ResultAll primitive roots
g^k with gcd(k, φ(n)) = 1
2, 6, 7, 11
CheckVerify by direct counting
Computing successive powers of 2 modulo 13 returns to 1 only after 12 steps = φ(n), so it generates every unit.
n = 8 (none)
- Modulus n:
8 - Check my own g (optional, 0 = skip):
0
Primitive roots of 8
None exist
No element has order φ(8), so there is nothing to find. Try a prime modulus or a prime power.
Step-by-step solution
Formula used
g is a primitive root mod n when its multiplicative order equals φ(n)
CalculateFactor the modulus
8 = 2^3
CalculateDoes a primitive root exist?
Primitive roots exist exactly for n = 1, 2, 4, p^k, 2p^k (p an odd prime)
8 is not of the form 1, 2, 4, p^k or 2p^k, so no primitive root exists: the group of units is not cyclic.
n = 1000003
- Modulus n:
1000003 - Check my own g (optional, 0 = skip):
0
Number of primitive roots
333332
φ(φ(n)) = φ(1000002)
The full list is shown only when φ(n) ≤ 200 000. The smallest root and the count are exact for any size.
Step-by-step solution
Formula used
g is a primitive root mod n ⇔ ord_n(g) = φ(n)
Test: g^(φ(n)/q) ≢ 1 (mod n) for every prime q | φ(n)
Number of primitive roots (when any exist) = φ(φ(n))
CalculateFactor the modulus
1000003 = 1000003
CalculateDoes a primitive root exist?
Primitive roots exist exactly for n = 1, 2, 4, p^k, 2p^k (p an odd prime)
1000003 has the required form, so the group of units modulo 1000003 is cyclic.
CalculateCompute φ(n) and factor it
g is a primitive root ⇔ g^(φ/q) ≢ 1 (mod n) for every prime q dividing φ(n)
φ(1000003) = 1000002
φ(n) = 2 × 3 × 166667
Primes q dividing φ(n): 2, 3, 166667
ResultTest g = 2
No power equals 1, so 2 is a primitive root.
| prime q | φ/q | g^(φ/q) mod 1000003 |
|---|
| 2 | 500001 | 1000002 |
| 3 | 333334 | 499501 |
| 166667 | 6 | 64 |
CalculateCount the primitive roots
count = φ(φ(n))
φ(1000002) = 333332
Frequently asked questions
What is the smallest primitive root of 23?
It is 5. The number 2 has order 11 modulo 23, and 3 has order 11 too, while 5 has the full order 22 = φ(23).
How many primitive roots does a prime p have?
Exactly φ(p − 1). For p = 11 that is φ(10) = 4, namely 2, 6, 7 and 8.
Why does 8 have no primitive root?
The units modulo 8 are 1, 3, 5, 7 and each of them squares to 1, so no element has order φ(8) = 4. The group of units is not cyclic.
What is the order of an element?
The smallest positive k with g^k ≡ 1 (mod n). It always divides φ(n). Enter a value of g in the calculator to see its order.