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, a², a³, … 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, x², …, x⁶ 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.