Orders and quadratic residues · Definition

Primitive root

elementary number theoryorders and quadratic residues

Before you start you need to know

Primitive roots allow the entire multiplicative group of residues to be described with a single generator. They appear in the study of power congruences and quadratic residues.

Definition

A primitive root modulo \(n\) is an integer \(g\) whose multiplicative order modulo \(n\) equals \(\varphi(n)\), so that its powers run through all residues coprime to \(n\).

\[\operatorname{ord}_n(g)=\varphi(n)\]

If \(g\) is a primitive root modulo \(n\), then \(\gcd(g,n)=1\) and the powers \(g^0,g^1,\dots,g^{\varphi(n)-1}\) are pairwise incongruent modulo \(n\). Hence the group of units modulo \(n\) is cyclic whenever a primitive root exists. This property is used to solve congruences of the form \(x^k\equiv a \pmod n\) via discrete logarithms.

Guiding example: modulo \(7\), \(\varphi(7)=6\). Since \(3^1=3\), \(3^2=2\), \(3^3=6\), \(3^6\equiv 1\) and no smaller exponent gives 1, the order of 3 is 6, so 3 is a primitive root modulo 7.

Typical error: assuming every unit is a primitive root. For instance, 2 has order 3 modulo 7, so it does not generate the whole group, even though it is coprime to 7.

Think about it

Why is \(2\) not a primitive root modulo \(7\) even though it is coprime to \(7\)?

Because its order modulo \(7\) is \(3\), not \(\varphi(7)=6\).

Exercises 10

  1. What is \(\varphi(9)\)?
  2. What does it mean for \(g\) to be a primitive root modulo \(n\)?
  3. If \(g\) is a primitive root modulo \(n\), how many distinct powers of \(g\) modulo \(n\) are there?
  4. Is 3 a primitive root modulo 7?
  5. What is the order of 2 modulo 5?
  6. Is 2 a primitive root modulo 7?
  7. For which of the moduli 8, 9, 7 or 5 does no primitive root exist?
  8. Which of the numbers 1, 2 or 4 is a primitive root modulo \(5\)? Note that \(\varphi(5)=4\).
  9. How many primitive roots modulo 7 exist?
  10. Give a counterexample showing that not every integer coprime to \(n\) is a primitive root, taking \(n=11\) and computing the order of 10.

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 8
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 2