Exercise · ZW-PRIMITIVE-ROOT-010 · ★★★ Advanced
Give a counterexample showing that not every integer coprime to \(n\) is a primitive root, taking \(n=11\) and computing the order of 10.
Choose one option.
Show answer
- B. 2
Explanation
Since \(10\equiv -1 \pmod{11}\), \(10^2\equiv 1\), so its order is 2, far from \(\varphi(11)=10\).
Review the concept: Primitive root
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)\]
More practice problems: primitive root
- ZW-PRIMITIVE-ROOT-001 What is φ(9)?
- ZW-PRIMITIVE-ROOT-002 What does it mean for g to be a primitive root modulo n?
- ZW-PRIMITIVE-ROOT-003 If g is a primitive root modulo n, how many distinct powers of g modulo n are there?
- ZW-PRIMITIVE-ROOT-004 Is 3 a primitive root modulo 7?
- ZW-PRIMITIVE-ROOT-005 What is the order of 2 modulo 5?
- ZW-PRIMITIVE-ROOT-006 Is 2 a primitive root modulo 7?
- ZW-PRIMITIVE-ROOT-007 For which of the moduli 8, 9, 7 or 5 does no primitive root exist?
- ZW-PRIMITIVE-ROOT-008 Which of the numbers 1, 2 or 4 is a primitive root modulo 5? Note that φ(5)=4.