Eine ganze Zahl g, deren Potenzen g^k modulo N (reduziert) alle zu N teilerfremden Restklassen erzeugen; äquivalent: g erzeugt die multiplikative Gruppe (Z/NZ)^×.

Prinzip

Ist (Z/NZ)^× zyklisch, so besitzt ein Element g die multiplikative Ordnung φ(N) und seine Potenzen listen alle Einheiten modulo N auf.

Demonstration

Für N = 7 ist 3 eine Primitivwurzel, denn die Potenzen 3^1,...,3^6 modulo 7 ergeben 3,2,6,4,5,1 und damit alle sechs Einheiten; 3 hat somit die Ordnung φ(7)=6.

Fehlanwendung

Fälschlicherweise zu behaupten, g sei eine Primitivwurzel, obwohl g nicht teilerfremd zu N ist oder (Z/NZ)^× nicht zyklisch ist (z. B. N = 8), führt zu falschen Schlussfolgerungen über die Erzeugung aller Einheiten.

Konsequenz

Existiert eine Primitivwurzel, so liefert der diskrete Logarithmus bezüglich dieser Wurzel eine Bijektion zwischen (Z/NZ)^× und Z/φ(N)Z und ermöglicht Argumente auf Basis der zyklischen Struktur.

Umkehrung

Das Gegenstück ist ein Element, dessen Potenzen nur eine echte Untergruppe von (Z/NZ)^× erzeugen (z. B. ein Element mit Ordnung, die einen echten Teiler von φ(N) teilt), und somit nicht alle teilerfremden Reste erreichen.

Abgrenzung

Primitivwurzeln existieren für N = 1, 2, 4, p^k und 2p^k mit ungerader Primzahl p; für allgemeine zusammengesetzte N existieren sie nicht. Das Konzept gilt nur für zu N teilerfreie ganze Zahlen und die Einheitengruppe modulo N.

Semantische Spannung

Man darf Primitivwurzel nicht mit einem Erzeuger einer additiven Gruppe oder einem beliebigen Element maximaler Ordnung in einem Unterring verwechseln; 'primitiv' meint hier Erzeuger der gesamten multiplikativen Einheitengruppe, falls diese zyklisch ist.

Synthese

Eine Primitivwurzel modulo N ist eine ganze Zahl, die, falls vorhanden, die Einheitengruppe modulo N zu einer zyklischen Gruppe macht, deren Potenzen alle invertierbaren Reste durchlaufen.