## [Primitivwurzel Modulo N](/de/node/61974) Definition 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 Prinzip Ist (Z/NZ)^× zyklisch, so besitzt ein Element g die multiplikative Ordnung φ(N) und seine Potenzen listen alle Einheiten modulo N auf. ## Demonstration 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 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 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 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 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 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 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.