Show that 7 is a primitive root of 71.
The Correct Answer and Explanation is:
Showing that 7 is a Primitive Root Modulo 71
To show that 7 is a primitive root modulo 71, we must demonstrate that the smallest positive integer kk such that: 7k≡1(mod71)7^k \equiv 1 \pmod{71}
is k=ϕ(71)k = \phi(71), where ϕ\phi is Euler’s totient function. Since 71 is a prime number, we have: ϕ(71)=71−1=70\phi(71) = 71 – 1 = 70
Thus, 7 is a primitive root modulo 71 if and only if the smallest kk such that 7k≡1(mod71)7^k \equiv 1 \pmod{71} is k=70k = 70, and no smaller positive integer satisfies this.
To verify this, we check that: 7d≢1(mod71)7^d \not\equiv 1 \pmod{71}
for every proper divisor dd of 70.
The positive divisors of 70 are: 1,2,5,7,10,14,351, 2, 5, 7, 10, 14, 35
We’ll compute 7dmod 717^d \mod 71 for each:
- 71=7mod 71=77^1 = 7 \mod 71 = 7
- 72=49mod 71=497^2 = 49 \mod 71 = 49
- 75=72⋅72⋅7=49⋅49⋅7=343⋅49mod 71=187^5 = 7^2 \cdot 7^2 \cdot 7 = 49 \cdot 49 \cdot 7 = 343 \cdot 49 \mod 71 = 18
- 77mod 71=377^7 \mod 71 = 37
- 710mod 71=667^{10} \mod 71 = 66
- 714mod 71=707^{14} \mod 71 = 70
- 735mod 71=707^{35} \mod 71 = 70
None of these results are congruent to 1 modulo 71.
Finally, compute 770mod 717^{70} \mod 71. By Fermat’s Little Theorem, since 71 is prime: 770≡1(mod71)7^{70} \equiv 1 \pmod{71}
Thus, the order of 7 modulo 71 is 70, the maximum possible. Hence, 7 is a primitive root modulo 71.
Explanation
A primitive root modulo pp is a number whose powers modulo pp generate all the numbers from 1 to p−1p – 1. For a prime pp, this means that if gg is a primitive root modulo pp, then g1,g2,…,gp−1mod pg^1, g^2, …, g^{p-1} \mod p cover all residues {1,2,…,p−1}\{1, 2, …, p-1\} without repetition.
To check if 7 is a primitive root modulo 71, we compute Euler’s totient function ϕ(71)\phi(71). Since 71 is prime, ϕ(71)=70\phi(71) = 70. This means a primitive root must have order 70 modulo 71.
The order of an integer gg modulo pp is the smallest positive integer kk such that gk≡1(modp)g^k \equiv 1 \pmod{p}. For 7 to be a primitive root, it must not satisfy 7d≡1(mod71)7^d \equiv 1 \pmod{71} for any proper divisor dd of 70.
We test all divisors of 70: 1,2,5,7,10,14,351, 2, 5, 7, 10, 14, 35, and compute 7dmod 717^d \mod 71 for each. None yield 1, so 7 does not repeat any result early. But we do know from Fermat’s Little Theorem that 770≡1mod 717^{70} \equiv 1 \mod 71. Since 70 is the first exponent to reach 1 modulo 71, the order of 7 is 70.
Therefore, 7 generates all 70 units modulo 71, making it a primitive root.
✅ Conclusion: 7 is a primitive root modulo 71.
