primitive root modulo calculator

What is a primitive root modulo n?

A number g is a primitive root modulo n if powers of g generate every number that is coprime to n. In group language, g is a generator of the multiplicative group (ℤ/nℤ)*.

For prime moduli, primitive roots are especially common in number theory and cryptography. For example, modulo 17, the number 3 is a primitive root because: 3, 3², 3³, ..., 3¹⁶ (mod 17) cycles through all nonzero residues.

When do primitive roots exist?

Primitive roots exist modulo n only for these forms:

• n = 2
• n = 4
• n = p^k where p is an odd prime and k ≥ 1
• n = 2p^k where p is an odd prime and k ≥ 1

If your input does not match one of these forms, the calculator will correctly report that no primitive roots exist.

How this calculator works

1) Compute Euler's totient

The size of the multiplicative group modulo n is φ(n). Any primitive root must have order exactly φ(n).

2) Use the order test efficiently

Let q run through distinct prime divisors of φ(n). A candidate g is primitive iff:

g^(φ(n)/q) mod n ≠ 1 for every such q, and gcd(g, n) = 1.

3) Generate all primitive roots

If r is one primitive root, then all primitive roots are r^k mod n where 1 ≤ k ≤ φ(n) and gcd(k, φ(n)) = 1.

Example

Try n = 17. You should get primitive roots such as: 3, 5, 6, 7, 10, 11, 12, 14. There are 8 in total, matching φ(φ(17)) = φ(16) = 8.

Why this matters

• Useful in modular exponentiation and discrete logarithm problems.
• Shows up in Diffie-Hellman style constructions over finite fields.
• Great for building intuition in abstract algebra and elementary number theory.

Notes & limitations

• This is a browser-based educational tool optimized for small-to-medium inputs.
• Very large values of n can be slow because integer factorization is hard.
• All arithmetic is exact for supported input range in this implementation.