Skip to content
OneKitly

Seven Has Two Primitive Roots and Eight Has None

Published 10/27/2026 · 3 min read · Everyday calculators

Lena Hoffmann

Lena Hoffmann — Science & education writer at OneKitly

Mathematics · Physics

Checked against 2 sources

View profile →
In short

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.

Advertisement

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.

How many
Which moduli have generators
ModulusGeneratorsHow many
73, 52
92, 52
112, 6, 7, 84
8, 12, 15none0
Primitive root calculatorFind the primitive roots modulo n — the generators g whose powers g¹, g², … run through every number coprime to n before repeating (order equal to φ(n)). Primitive roots exist only when n is 1, 2, 4, pᵏ or 2pᵏ for an odd prime p; the tool reports the smallest one, the exact count φ(φ(n)) and lists them. They are the backbone of discrete-logarithm cryptography and Diffie–Hellman key exchange.Try the tool →
Advertisement

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?