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
Fix n >= 2. A unit modulo n is a remainder coprime to n; phi(n) counts these units. The order of a unit a is the least positive k with a^k congruent to 1 modulo n. Its order divides phi(n). To see this, divide phi(n) by the order. Euler's theorem makes the remainder exponent return 1 too, so minimality forces that remainder to be zero.
A primitive root is a unit of order phi(n). Its powers reach every unit. Modulo 11, successive powers of 7 give 7, 5, 2, 3, 10, 4, 6, 9, 8, 1. The first return to 1 is at exponent 10. Since phi(11) = 10, 7 is a primitive root.
Check coprimality first. Multiply by the base and reduce modulo n until 1 first appears. The candidate is primitive exactly when that exponent equals phi(n). A shorter test sets m = phi(n): a unit is primitive if and only if a^(m/q) differs from 1 modulo n for every prime divisor q of m. Any proper divisor d of m divides m/q for at least one such q.
For n >= 2, primitive roots exist exactly for n = 2, 4, p^k or 2p^k, where p is an odd prime and k >= 1. For example, 27 and 54 have the required forms. Powers of 2 greater than 4 do not. To disprove existence directly, show that every unit has order smaller than phi(n).
If g is primitive and m = phi(n), exponents 0 through m - 1 index all units once. To solve g^t congruent to b, locate b in this power list. All solutions for t agree modulo m. Multiplication of units adds their exponent indices. For example, modulo 11, 7^8 gives 9, so 7^t is congruent to 9 exactly when t is congruent to 8 modulo 10.
If g has order m, then g^r has order m/gcd(m,r). Indeed, (g^r)^k = g^(rk) returns 1 exactly when m divides rk. The least positive k satisfying this is m/gcd(m,r). This lets you find the order of a generator's power without building another full power list.
Order is the first positive exponent returning 1. A primitive root has order phi(n), so its powers reach every unit.
The lesson, questions, worked solutions and base flashcards were written for this dataset.
The readings and extra questions were written for this dataset. The flashcards retain imported facts-collection material with corrections. The linked videos are credited to Khan Academy. Terms for the retained imported material have not been verified.
More to read
Check the candidate's common factors
Order is defined here for units modulo n, with n >= 2. A unit has greatest common divisor 1 with n. If a and n share a prime factor, every positive power of a retains that factor and cannot be congruent to 1 modulo n. For instance, 6 cannot be a primitive root modulo 15 because both numbers are divisible by 3. This check can rule out a candidate before you compute any powers.
Record the first return to 1
For a unit a, start with exponent 1 and repeatedly multiply the current remainder by a. Reduce modulo n after every multiplication. Modulo 14, the powers of 3 give 3, 9, 13, 11, 5, 1. The first 1 occurs at exponent 6, so the order is 6. The cycle then repeats. A later return, such as exponent 12, does not change the order. Euler's theorem guarantees a return by exponent phi(n).
Use prime divisors to test a generator
Suppose a is a unit and m = phi(n). Test a^(m/q) for each prime divisor q of m. Any result congruent to 1 rules out order m. If none is 1, the order is m. This covers every possible smaller order d: write m = ds. When s > 1, it has a prime divisor q, and m/q is a multiple of d. That test exponent would therefore return 1. You need the prime divisors of m, not every exponent below it.
Calculate a test power by squaring
Repeated squaring builds powers with exponents 1, 2, 4, 8 and so on. Keep only the remainder at each stage. Modulo 17, 3^2 gives 9, 3^4 gives 13, and 3^8 gives 16. To obtain exponent 10, combine exponents 8 and 2. Thus 3^10 has the remainder of 16 times 9, which is 8 modulo 17. The same procedure evaluates the larger powers needed in a primitive-root test.
Factor the modulus before searching
For n >= 2, the complete list of moduli admitting primitive roots is 2, 4, p^k and 2p^k, where p is an odd prime and k is a positive integer. Both 25 and 50 fit the list. The modulus 12 does not. Its four units are 1, 5, 7 and 11; squaring any of them gives remainder 1. Their orders are at most 2, so none has the order 4 needed to generate every unit.
Explore more
2 · Watch
Take it off screen
Where it sits
Learn first
Optional connections
This opens up
14 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.