Seven Has Two Primitive Roots and Eight Has None
Published 10/27/2026 · 3 min read · Everyday calculators
Lena Hoffmann — Science & education writer at OneKitly
Mathematics · Physics
Checked against 2 sources
A primitive root modulo n is a number whose powers run through every value coprime to n before returning to one. Modulo 7 the number 3 does it: 3, 2, 6, 4, 5, 1 — all six residues, in a scrambled order, then back to the start. Five does the same, and nothing else does, so there are two. Modulo 11 there are four generators, and modulo 8 there are none at all: no number's powers reach every candidate, because the structure there splits into two independent halves rather than forming a single cycle. The count, when generators exist, is φ(φ(n)) — for 7 that is φ(6) = 2, and for 11 it is φ(10) = 4.
Modulo 7 the numbers 3 and 5 each generate every non-zero value by repeated multiplication. Modulo 8 nothing does, and modulo 11 there are four generators.
The moduli that work are a short list
Generators exist only for 1, 2, 4, an odd prime raised to any power, and twice such a power — nothing else. That rules out 8, 12 and 15 immediately, and it is why 9 works while 8 does not despite both being small powers. The reason is that the multiplicative structure modulo anything else decomposes into independent pieces, and no single element can generate a product of independent cycles. It is a rare case where the classification is complete, short, and can be checked against the calculator in a minute — which makes it a good example of a theorem being more useful than a search.
What a generator is for
Having one turns multiplication into addition. Every non-zero value can be written as the generator raised to some power, so multiplying two values corresponds to adding their exponents — the same trick logarithms play with ordinary numbers, in a finite setting. That correspondence is what key-exchange protocols exploit: raising a shared generator to a secret exponent is easy, and recovering the exponent from the result appears to be hard, so two parties can agree on a value neither of them transmitted. The whole construction depends on the group being a single cycle, which is exactly what a primitive root guarantees.
| Modulus | Generators | How many |
|---|---|---|
| 7 | 3, 5 | 2 |
| 9 | 2, 5 | 2 |
| 11 | 2, 6, 7, 8 | 4 |
| 8, 12, 15 | none | 0 |
Frequently asked questions
- Is there a formula for the smallest generator?
- None is known, and the search is done by trial. Candidates are tested in order and each test is cheap — it is enough to check that the candidate raised to the totient divided by each prime factor is not one — but there is no way to predict which candidate will succeed. In practice the smallest generator is almost always a very small number, two or three or five, and heuristics say it should grow extremely slowly with the modulus; that expectation is well supported and unproven, which is the recurring shape of results in this corner of the subject.
- Why does the number of generators depend on φ(φ(n))?
- Because once one generator is found, every other is one of its powers, and a power generates the whole cycle exactly when its exponent is coprime to the cycle's length. The cycle has length φ(n), so the number of usable exponents is φ(φ(n)) by the same counting argument that defines the totient in the first place. Modulo 7 the cycle has length 6, the exponents coprime to 6 are 1 and 5, and the two generators 3 and 5 are the first generator raised to those powers. The double application of the same function is not a coincidence — it is the same question asked about the exponents instead of the values.
Articles you may find interesting
All guides →Related tools
Sources
Spotted a mistake in this article?