Zum Inhalt springen
OneKitly

Sieben hat zwei Primitivwurzeln, acht keine

Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner

Lena Hoffmann

Lena Hoffmann — Redakteurin Wissenschaft & Bildung bei OneKitly

Mathematik · Physik

Anhand von 2 Quellen geprüft

Profil ansehen →
Kurz gesagt

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.

Werbung

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.

Wie viele
Welche Moduln Erzeuger haben
ModulErzeugerWie viele
73, 52
92, 52
112, 6, 7, 84
8, 12, 15keine0
Primitivwurzel-RechnerFinde die Primitivwurzeln modulo n — die Erzeuger g, deren Potenzen g¹, g², … alle zu n teilerfremden Zahlen durchlaufen, bevor sie sich wiederholen (Ordnung gleich φ(n)). Primitivwurzeln existieren nur, wenn n gleich 1, 2, 4, pᵏ oder 2pᵏ für eine ungerade Primzahl p ist; das Tool nennt die kleinste, die exakte Anzahl φ(φ(n)) und listet sie. Sie sind das Rückgrat der Kryptografie mit diskretem Logarithmus und des Diffie–Hellman-Schlüsseltauschs.Tool ausprobieren →
Werbung

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 →
ErklärungSieben hoch 256 hat 217 Stellen, und man schreibt keine davon7²⁵⁶ mod 13 ist 9, und 2¹⁰⁰⁰ mod 1.000.000.007 ist 688.423.210. Beides ergibt sich aus acht bzw. zehn Quadrierungen, wobei keine Zahl der Rechnung das Quadrat des Moduls übersteigt.ErklärungEine Funktion, die nur −1, 0 oder 1 antwortetDie Möbius-Funktion liefert 0 für 12 und 49, −1 für 30 und 105 und 1 für 6. Drei mögliche Antworten kodieren das gesamte Faktorisierungsmuster einer Zahl.ErklärungEine Primzahl ist zu fast allem unter ihr teilerfremdφ(97) = 96, der größte Wert, den eine Zahl unter hundert erreichen kann. φ(36) ist 12 und φ(100) ist 40 — je mehr verschiedene Primfaktoren eine Zahl hat, desto weniger Gefährten behält sie.ErklärungModulare Division funktioniert nur, wenn die Zahlen keinen Faktor teilen3 hat modulo 7 ein Inverses — es ist 5, denn 15 lässt Rest 1. 4 hat modulo 8 keines, denn beide teilen den Faktor 4, und kein Vielfaches von 4 lässt je Rest 1.ErklärungSiebenundzwanzig braucht 111 Schritte, sechsundzwanzig zehnHalbiere, wenn gerade; verdreifache und addiere eins, wenn ungerade. Von 27 aus steigt die Folge auf 9.232, bevor sie fällt; von 26 aus ist sie nach zehn Zügen vorbei.ErklärungEine unglückliche Zahl fällt stets in dieselbe AchterschleifeQuadriere die Ziffern und addiere. 19 erreicht die 1 in vier Schritten. Die 4 nicht, und nichts anderes Scheiterndes auch nicht — jedes Scheitern landet in 4, 16, 37, 58, 89, 145, 42, 20 und kreist für immer.

Ähnliche Tools

Quellen

Hast du einen Fehler in diesem Artikel entdeckt?