Primitive Root Calculator

Primitive roots are important in Diffie-Hellman, discrete logarithms, and cyclic groups.

Use the result as a learning aid. For classwork, still show the formula and intermediate reasoning so the final answer is not just a black-box number.

For a modulus n, the invertible residue classes form the multiplicative group of units modulo n. A number g is a primitive root modulo n when the powers g¹,g²,… generate every unit before returning to 1. Equivalently, the multiplicative order of g equals Euler’s totient φ(n).

The calculator repeatedly multiplies by g modulo n and records the residues until 1 reappears. If the number of distinct generated units equals the total number of units, g is primitive. The condition gcd(g,n)=1 is necessary because only units can belong to the multiplicative group.

Not every modulus has primitive roots. A classical theorem says primitive roots exist exactly for n=1,2,4,pᵏ, and 2pᵏ where p is an odd prime. For many classroom examples, a prime modulus is used; then every nonzero residue is a unit and a primitive root has order p−1.

A quick prime-modulus test can use factors of p−1. For prime p, g is primitive exactly when g^((p−1)/q) is not congruent to 1 modulo p for every prime factor q of p−1. This factor test is often faster than listing every power when p is large, although enumerating residues is excellent for learning.

When checking a power sequence by hand, reduce after every multiplication. For example, modulo 7 the sequence for g=3 is 3, 9≡2, 6, 18≡4, 12≡5, 15≡1. Keeping residues small prevents arithmetic growth and makes it obvious when the cycle returns to 1.