Primitivwurzel

In der Zahlentheorie heißt eine ganze Zahl a Primitivwurzel \mod p, wenn die Restklasse a + p\mathbb{Z} die prime Restklassengruppe ( \mathbb{Z} /p\mathbb{Z} )^* erzeugt. Hierbei steht \mod wie üblich für den Modulo-Operator (s. dort).

Der Ausdruck a^t\mod p nimmt für 0 \le t \le p-2 alle Werte aus \{1,\ldots,p-1\} (in scheinbar zufälliger Reihenfolge) an.

Die Anzahl der Primitivwurzeln von p ist φ(φ(p)). Hierbei ist φ() die Eulersche φ-Funktion


Kategorie:Zahlentheorie

Existenz von Primitivwurzeln

Nach einem Satz von Gauß (nach C. F. Gauß) existieren genau dann Primitivwurzeln modulo m, wenn m gleich 1,2,4,pα,2pα mit einer ungeraden Primzahl p und einer natürlichen Zahl α ist.

See also: Primitivwurzel, Carl Friedrich Gauß, Eulersche φ-Funktion, Modulo, Prime Restklassengruppe, Restklasse, Zahlentheorie