Sieben hat zwei Primitivwurzeln, acht keine
Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner
Lena Hoffmann — Redakteurin Wissenschaft & Bildung bei OneKitly
Mathematik · Physik
Anhand von 2 Quellen geprüft
Eine Primitivwurzel modulo n ist eine Zahl, deren Potenzen jeden zu n teilerfremden Wert durchlaufen, bevor sie zur Eins zurückkehren. Modulo 7 schafft das die 3: 3, 2, 6, 4, 5, 1 — alle sechs Reste in verwürfelter Reihenfolge, dann zurück zum Anfang. Die 5 tut dasselbe, sonst nichts; es sind also zwei. Modulo 11 gibt es vier Erzeuger, modulo 8 gar keinen: Die Potenzen keiner Zahl erreichen alle Kandidaten, denn dort zerfällt die Struktur in zwei unabhängige Hälften, statt einen einzigen Zyklus zu bilden. Die Anzahl beträgt, wenn Erzeuger existieren, φ(φ(n)) — für 7 also φ(6) = 2, für 11 φ(10) = 4.
Modulo 7 erzeugen die Zahlen 3 und 5 durch wiederholtes Multiplizieren jeweils jeden von null verschiedenen Wert. Modulo 8 gelingt das keiner, modulo 11 gibt es vier Erzeuger.
Die funktionierenden Moduln sind eine kurze Liste
Erzeuger gibt es nur für 1, 2, 4, eine beliebige Potenz einer ungeraden Primzahl und das Doppelte einer solchen Potenz — sonst nichts. Das schließt 8, 12 und 15 sofort aus und erklärt, warum 9 funktioniert und 8 nicht, obwohl beide klein sind. Der Grund: Die multiplikative Struktur modulo allem anderen zerfällt in unabhängige Teile, und kein einzelnes Element kann ein Produkt unabhängiger Zyklen erzeugen. Ein seltener Fall, in dem die Klassifikation vollständig, kurz und binnen einer Minute gegen den Rechner prüfbar ist — ein gutes Beispiel dafür, dass ein Satz nützlicher ist als eine Suche.
Wozu ein Erzeuger dient
Einen zu haben verwandelt Multiplikation in Addition. Jeder von null verschiedene Wert lässt sich als Potenz des Erzeugers schreiben; zwei Werte zu multiplizieren heißt also, ihre Exponenten zu addieren — derselbe Trick, den Logarithmen bei gewöhnlichen Zahlen spielen, nur im Endlichen. Genau diese Entsprechung nutzen Schlüsselaustauschprotokolle: Einen gemeinsamen Erzeuger in einen geheimen Exponenten zu erheben ist leicht, den Exponenten aus dem Ergebnis zurückzugewinnen scheint schwer — zwei Parteien können sich so auf einen Wert einigen, den keine übertragen hat. Die ganze Konstruktion hängt daran, dass die Gruppe ein einziger Zyklus ist, und genau das garantiert eine Primitivwurzel.
| Modul | Erzeuger | Wie viele |
|---|---|---|
| 7 | 3, 5 | 2 |
| 9 | 2, 5 | 2 |
| 11 | 2, 6, 7, 8 | 4 |
| 8, 12, 15 | keine | 0 |
Häufige Fragen
- Gibt es eine Formel für den kleinsten Erzeuger?
- Keine ist bekannt, und die Suche erfolgt durch Probieren. Kandidaten werden der Reihe nach getestet, und jeder Test ist billig — es genügt zu prüfen, dass der Kandidat, erhoben in die Phi-Funktion geteilt durch jeden Primfaktor, nicht eins ergibt — doch lässt sich nicht vorhersagen, welcher Kandidat gelingt. Praktisch ist der kleinste Erzeuger fast immer eine sehr kleine Zahl, zwei, drei oder fünf, und Heuristiken sagen ein äußerst langsames Wachstum mit dem Modul voraus; diese Erwartung ist gut gestützt und unbewiesen — die wiederkehrende Gestalt der Resultate in dieser Ecke des Fachs.
- Warum hängt die Erzeugerzahl von φ(φ(n)) ab?
- Weil, sobald ein Erzeuger gefunden ist, jeder andere eine seiner Potenzen ist, und eine Potenz genau dann den ganzen Zyklus erzeugt, wenn ihr Exponent zur Zykluslänge teilerfremd ist. Der Zyklus hat die Länge φ(n); die Zahl brauchbarer Exponenten ist also φ(φ(n)), nach demselben Abzählargument, das die Phi-Funktion überhaupt definiert. Modulo 7 hat der Zyklus die Länge 6, die zu 6 teilerfremden Exponenten sind 1 und 5, und die beiden Erzeuger 3 und 5 sind der erste Erzeuger in diesen Potenzen. Die doppelte Anwendung derselben Funktion ist kein Zufall — es ist dieselbe Frage, gestellt über die Exponenten statt über die Werte.
Artikel, die dich interessieren könnten
Alle Ratgeber →Ähnliche Tools
Quellen
Hast du einen Fehler in diesem Artikel entdeckt?