ConverterHub

Primitive Root Calculator

Enter a modulus n to find its smallest primitive root.

Result

5
22
10

How it is calculated

For a whole modulus n from 2 to 100,000 the tool computes Euler's totient φ(n), the count of numbers below n that share no factor with n. It then tries g = 1, 2, 3, … that are coprime to n, and for each one repeatedly multiplies mod n until the value returns to 1, counting the steps. The first g whose count equals φ(n) is the smallest primitive root. It also reports φ(n) as the required order and the number of primitive roots, which is φ(φ(n)). If no g works, as for n = 8 or n = 100, no result appears: primitive roots exist only for n = 2, 4, p^k and 2p^k with p an odd prime. Non-integers, n below 2 and n above 100,000 are rejected.

Worked example

Take n = 23, a prime, so φ(23) = 22 and a primitive root must have order 22. Trying 1 gives order 1. Trying 2 gives order 11, because 2 to the power 11 is 2048, which is 1 mod 23. The numbers 3 and 4 also have order 11. Trying 5 gives order 22: its powers run through all 22 nonzero residues before returning to 1. So the smallest primitive root is 5. The number of primitive roots is φ(22) = 10.

Try this example →

Common mistakes

  • Confusing a primitive root with a primitive root of unity or with a square root. Here g must generate every number coprime to n through its powers.
  • Assuming every modulus has one. Moduli such as 8, 12 and 100 have none, and the tool then returns no result rather than a wrong answer.
  • Stopping at the first g with a large order. A primitive root needs order exactly φ(n), and for n = 23 the values 2, 3 and 4 all stop at order 11.
  • Entering a number above 100,000 or a decimal. Only whole moduli from 2 to 100,000 are accepted.
  • Expecting the largest or a random primitive root. The tool returns only the smallest; other roots are powers of it with exponents coprime to φ(n).

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 (trivially), 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 whole modulus n from 2 to 100,000 and this calculator finds its smallest primitive root, along with φ(n) and the number of primitive roots. If no primitive root exists for that n, it returns no result.

Was this helpful?

You can pick up to 3 reactions.

Comments

  • Be the first to comment.

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators