Lexikon der Mathematik: Primitivwurzel modulo m
zu m teilerfremde ganze Zahl a, deren Ordnung modulo m gleich φ(m) ist, wobei mit letzterem die Eulersche φ-Funktion bezeichnet ist.
φ(m) ist die Anzahl der zu m teilerfremden natürlichen Zahlen < m, also gleich der Anzahl der primen Restklassen modulo m. Ist die Ordnung modulo m einer Zahl a gleich φ(m), so treffen die Potenzen a, a2, a3, … also jede prime Restklasse modulo m. Eine ganze Zahl a ist damit genau dann eine Primitivwurzel modulo m, wenn die Restklasse a (mod m) die prime Restklassengruppe modulo m (diese Gruppe wird mit (ℤ/mℤ)× bezeichnet) erzeugt.
Zwei Beispiele:
1. Die Gruppe (ℤ/18ℤ)× besteht aus den Restklassen
1, 5, 7, 11, 13, 17 (mod 18).
Um alle Primitivwurzeln modulo 18 zu finden, berechnen wir die Potenzen x, x2, …, x6 in der Arithmetik der Restklassen modulo m:
Die zu x = 5 und x = 11 gehörigen Zeilen durchlaufen die gesamte Gruppe, während jede der restlichen Zeilen nur einen Teil der Gruppenelemente enthält. Damit sind die Primitivwurzln modulo 18 gerade diejenigen ganzen Zahlen, die entweder ≡ 5 mod 18 oder ≡ 11 mod 18 sind.
2. Die Gruppe (ℤ/12ℤ)× besteht aus den φ(12) = 4 Restklassen
1, 5, 7, 11 (mod 12).
Hier hat jedes Element die Ordnung 2, also gibt es keine Primitivwurzel modulo 12.
Die Frage, zu welchen Moduln m es Primitivwurzeln gibt, wird durch einen Satz von Gauß vollständig beantwortet (Gauß, Satz von, über die Existenz von Primitivwurzeln modulo m). Wenn es überhaupt eine Primitivwurzel modulo m gibt, so besteht die Menge der Primitivwurzeln modulo m aus genau φ(φ(m)) Restklassen modulo m.
Ist m = p eine Primzahl, so gibt es stets Primitivwurzeln modulo p. Die folgende Tabelle enthält zu einigen kleinen Primzahlen jeweils eine vollständige Liste der Restklassen modulo p, die aus Primitivwurzeln modulo p bestehen:
Obwohl die Bestimmung der Primitivwurzeln modulo einer gegebenen Primzahl p leicht durchführbar ist, kann es sehr schwierig sein, allgemeine Eigenschaften dieser Tabelle (wenn man sie sich unendlich fortgesetzt denkt) zu beweisen. Beispielsweise ist die Artinsche Vermutung noch nicht bewiesen.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.