Primitive Root Calculator

About this calculator

A number g is a primitive root modulo n if its powers — g¹, g², g³, and so on — cycle through every number coprime to n before repeating, meaning the smallest exponent k for which g^k ≡ 1 (mod n) is exactly φ(n), Euler's totient function. In other words, a single primitive root generates the entire multiplicative group modulo n on its own. Primitive roots do not exist for every modulus: classical number theory (going back to Gauss) shows they exist only when n is 1, 2, 4, a power of an odd prime, or twice a power of an odd prime.

Primitive roots are a working tool in cryptography, not just a curiosity: Diffie–Hellman key exchange and the ElGamal cryptosystem both rely on the difficulty of the discrete logarithm problem in a group generated by a primitive root, and number-theoretic transforms used in fast, exact polynomial multiplication (relevant to some modern cryptographic and error-correction schemes) also depend on finding suitable primitive roots of a modulus.

Enter a modulus n and this calculator finds its smallest primitive root, if one exists, along with a note when no primitive root exists for that n.