Naar de inhoud
OneKitly

Seven Has Two Primitive Roots and Eight Has None

Gepubliceerd op 27-10-2026 · 3 min leestijd · Dagelijkse calculators

Lena Hoffmann

Lena Hoffmann — Redacteur wetenschap en onderwijs bij OneKitly

Wiskunde · Natuurkunde

Getoetst aan 2 bronnen

Profiel bekijken →
Kort gezegd

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.

Advertentie

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
Calculator voor primitieve wortelsZoek de primitieve wortels modulo n — de voortbrengers g waarvan de machten g¹, g², … elk getal doorlopen dat relatief priem is met n voordat ze zich herhalen (orde gelijk aan φ(n)). Primitieve wortels bestaan alleen als n gelijk is aan 1, 2, 4, pᵏ of 2pᵏ voor een oneven priemgetal p; de tool meldt de kleinste, het exacte aantal φ(φ(n)) en somt ze op. Ze vormen de ruggengraat van cryptografie met discrete logaritmen en van de sleuteluitwisseling van Diffie–Hellman.Probeer de tool →
Advertentie

Veelgestelde vragen

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.

Artikelen die je misschien interesseren

Alle gidsen →

Vergelijkbare tools

Calculator voor primitieve wortelsZoek de primitieve wortels modulo n — de voortbrengers g waarvan de machten g¹, g², … elk getal doorlopen dat relatief priem is met n voordat ze zich herhalen (orde gelijk aan φ(n)). Primitieve wortels bestaan alleen als n gelijk is aan 1, 2, 4, pᵏ of 2pᵏ voor een oneven priemgetal p; de tool meldt de kleinste, het exacte aantal φ(φ(n)) en somt ze op. Ze vormen de ruggengraat van cryptografie met discrete logaritmen en van de sleuteluitwisseling van Diffie–Hellman.Totiëntcalculator van Euler φ(n)Bereken de totiëntfunctie van Euler φ(n) — het aantal gehele getallen van 1 tot n die relatief priem zijn met n (geen andere deler dan 1 gemeen hebben). De tool ontbindt n in priemfactoren en past φ(n) = n·∏(1−1/p) toe over de verschillende priemfactoren, en laat de ontbinding, de formule en het aantal relatief prieme getallen zien. φ ligt onder RSA, de stelling van Euler en de orde van de multiplicatieve groep mod n.Calculator voor modulair machtsverheffenBereken aᵇ mod n efficiënt met snel machtsverheffen (kwadrateren en vermenigvuldigen) en grote gehele getallen, zodat zelfs astronomisch grote machten in een fractie van een seconde teruggebracht worden. De tool brengt een negatieve of te grote basis eerst naar het bereik 0…n−1, en ondersteunt negatieve exponenten zodra de basis inverteerbaar is modulo n. Dit is de kernbewerking achter RSA, Diffie–Hellman en priemtesten.ModulocalculatorBereken de rest en het quotiënt van een deling (modulo).

Bronnen

Een fout in dit artikel gezien?