Primitive Roots and the Units Modulo n
Ask when the units modulo n are generated by a single element, and settle which n admit one.
What a learner can do afterwards
- Compute the order of an element modulo n and relate it to the totient
- Find a primitive root modulo a small prime and use it to index the other units
- State which moduli have primitive roots and give a modulus that does not
1 · Read
Modulo n, the remainders coprime to n are called units. The order of a unit is the smallest k with a to the k equal to 1 modulo n, and it always divides phi of n. Powers of 2 modulo 5 go 2, 4, 3, 1, so the order of 2 is 4.
A primitive root is a unit whose order equals phi of n, so its powers list every unit. Modulo 5 the powers 2, 4, 3, 1 cover all four nonzero remainders, which makes 2 a primitive root there.
Test candidates by computing powers, reducing modulo n each time. Modulo 7, powers of 2 go 2, 4, 1, so the order is 3, while powers of 3 run 3, 2, 6, 4, 5, 1, reaching all six units. That makes 3, not 2, a primitive root modulo 7.
Only some moduli own primitive roots: 2, 4, prime powers, and twice prime powers. Modulo 8 has none, since every odd square is 1 there while phi of 8 is 4. Always check coprimality first: testing a non unit goes nowhere.
Order measures the wait until powers return to one, and a primitive root is a unit with the longest possible wait.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.