On Primitive Roots

Sei $n$ eine ganze Zahl, für die eine Primitivwurzel existiert. Die Gruppe $G=(\mathbb{Z}/n\mathbb{Z})^\ast$ ist demnach eine zyklische Gruppe der Ordnung $m=\varphi(n)$.

Sei $g$ eine Primitivwurzel modulo $n$. Per Definition ist $g$ ein Erzeuger von $G$, und es gilt $\text{ord}_n(g)=\varphi(n)$. Jedes Element $a \in G$ kann somit eindeutig als eine Potenz von $g$ dargestellt werden, d.h., es existiert ein eindeutiger Exponent $k \in \{1, 2, \dots, \varphi(n)\}$, sodass $a \equiv g^k \pmod{n}$.

Ein zentrales Resultat der Gruppentheorie besagt: Ist $h$ ein Element der Ordnung $m$ in einer endlichen Gruppe, so ist die Ordnung seiner Potenz $h^k$ gegeben durch die Formel:

Ein Element $a=g^k$ ist genau dann ebenfalls eine Primitivwurzel (also ein Erzeuger von $G$), wenn seine Ordnung gleich der Gruppenordnung $\varphi(n)$ ist. Wir wenden die Formel auf das Element $g$ an, dessen Ordnung $\text{ord}_n(g)=\varphi(n)$ ist:

Damit die Gleichung $\text{ord}_n(g^k)=\varphi(n)$ erfüllt ist, muss der Nenner des Bruchs auf der rechten Seite gleich 1 sein. Dies führt zu der notwendigen und hinreichenden Bedingung:

Die Frage nach der Anzahl der Primitivwurzeln ist nun auf ein reines Zählproblem zurückgeführt: Wie viele Exponenten $k$ im Bereich $1 \le k \le \varphi(n)$ sind teilerfremd zu $\varphi(n)$? Nach der Definition der Eulerschen phi-Funktion ist diese Anzahl exakt $\varphi(\varphi(n))$.

Zur zweiten Aussage:
Da $g$ eine Primitivwurzel ist, erzeugen seine Potenzen die gesamte Gruppe $(\mathbb{Z}/n\mathbb{Z})^\ast$. Folglich muss jede andere Primitivwurzel $h$ die Form $h \equiv g^k \pmod{n}$ für einen Exponenten $k$ im Bereich $1 \le k \le \varphi(n)$ haben. Wie vorher gezeigt wurde, ist ein Element der Form $g^k$ genau dann wieder eine Primitivwurzel (d.h., hat die Ordnung $\varphi(n)$), wenn der Exponent $k$ teilerfremd zur Gruppenordnung $\varphi(n)$ ist.

Zusammengenommen bedeutet dies, dass die Menge aller Primitivwurzeln genau die Menge der Potenzen $g^k$ ist, deren Exponenten $k$ die Bedingung $\text{ggT}(k, \varphi(n)) = 1$ erfüllen.

Wir zeigen zuerst, dass wenn $G$ zyklisch ist, $n$ eine der angegebenen Formen haben muss. Danach zeigen wir, dass für diese Formen von $n$ die Gruppe $G$ tatsächlich zyklisch ist.

$\Rightarrow$

Angenommen, $(\mathbb{Z}/n\mathbb{Z})^\ast$ ist zyklisch. Sei die Primfaktorzerlegung von $n$ gegeben durch $n = 2^k p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$.

Nach dem Chinesischen Restsatz gilt für die Gruppe:

Ein direktes Produkt von endlichen Gruppen ist genau dann zyklisch, wenn alle Faktorgruppen zyklisch sind und ihre Ordnungen paarweise teilerfremd sind.

Die Ordnungen der Faktorgruppen sind:

• $|\,(\mathbb{Z}/p_i^{k_i}\mathbb{Z})^\ast\,| = \varphi(p_i^{k_i}) = p_i^{k_i-1}(p_i-1)$. Da $p_i$ eine ungerade Primzahl ist, ist $p_i-1$ eine gerade Zahl. Die Ordnung ist also gerade.
• $|\,(\mathbb{Z}/2^k\mathbb{Z})^\ast\,| = \varphi(2^k) = 2^{k-1}$ (für $k \ge 1$).

Analysieren wir nun die Bedingungen für die Zyklizität:

1. Anzahl der ungeraden Primfaktoren ($r$): Wenn $r \ge 2$ (d.h., $n$ hat mindestens zwei verschiedene ungerade Primfaktoren), dann gibt es mindestens zwei Faktorgruppen (z.B. $(\mathbb{Z}/p_1^{k_1}\mathbb{Z})^\ast$ und $(\mathbb{Z}/p_2^{k_2}\mathbb{Z})^\ast$), deren Ordnungen beide gerade sind. Da ihre Ordnungen nicht teilerfremd sind, kann die Gesamtgruppe nicht zyklisch sein. Folgerung: $n$ kann höchstens einen ungeraden Primfaktor haben, also $r \le 1$. Somit muss $n$ die Form $n=2^k p^j$ haben.

2. Analyse der Form $n=2^k p^j$: Die Gruppe ist $(\mathbb{Z}/2^k p^j\mathbb{Z})^\ast \cong (\mathbb{Z}/2^k\mathbb{Z})^\ast\times (\mathbb{Z}/p^j\mathbb{Z})^\ast$. Die Ordnungen sind $\varphi(2^k)=2^{k-1}$ (für $k \ge 2$) und $\varphi(p^j)=p^{j-1}(p-1)$. Wenn $k \ge 2$, ist $\varphi(2^k)=2^{k-1}$ gerade. Da $\varphi(p^j)$ ebenfalls gerade ist, sind die Ordnungen nicht teilerfremd. In diesem Fall kann die Gruppe nicht zyklisch sein. Folgerung: Wenn $n$ einen ungeraden Primfaktor hat ($j \ge 1$), dann darf $k$ nicht größer oder gleich 2 sein. Es bleiben nur $k=0$ (ergibt $n=p^j$) und $k=1$ (ergibt $n=2p^j$).

3. Analyse des Falles ohne ungerade Primfaktoren ($n=2^k$): Wir müssen prüfen, für welche $k$ die Gruppe $(\mathbb{Z}/2^k\mathbb{Z})^\ast$ selbst zyklisch ist.

   • $k=0 \Rightarrow n=1$: $(\mathbb{Z}/1\mathbb{Z})^\ast = \{1\}$, zyklisch.
   • $k=1 \Rightarrow n=2$: $(\mathbb{Z}/2\mathbb{Z})^\ast = \{1\}$, zyklisch.
   • $k=2 \Rightarrow n=4$: $(\mathbb{Z}/4\mathbb{Z})^\ast = \{1, 3\}$. Mit Erzeuger 3, zyklisch.
   • $k \ge 3$: Die Gruppe $(\mathbb{Z}/2^k\mathbb{Z})^\ast$ ist isomorph zu $C_2\times C_{2^{k-2}}$. Da sie das direkte Produkt zweier Gruppen mit gerader Ordnung ist, ist sie nicht zyklisch. Man kann zeigen, dass für jedes Element $a \in (\mathbb{Z}/2^k\mathbb{Z})^\ast$ gilt: $a^{\varphi(2^k)/2} = a^{2^{k-2}} \equiv 1 \pmod{2^k}$. Es gibt also kein Element der Ordnung $\varphi(2^k)$.

Damit $(\mathbb{Z}/n\mathbb{Z})^\ast$ zyklisch ist, muss $n$ eine der Formen $1, 2, 4, p^k$ oder $2p^k$ haben.

$\Leftarrow$

Wir müssen zeigen, dass für die angegebenen Formen von $n$ die Gruppe $(\mathbb{Z}/n\mathbb{Z})^\ast$ zyklisch ist.

• Fälle $n=1, 2, 4$: Wie oben gesehen, sind die Gruppen $(\mathbb{Z}/1\mathbb{Z})^\ast$, $(\mathbb{Z}/2\mathbb{Z})^\ast$ und $(\mathbb{Z}/4\mathbb{Z})^\ast$ zyklisch.

• Fall $n=p^k$ ($p$ ungerade Primzahl, $k \ge 1$): Man zeigt, dass es eine Primitivwurzel modulo $p^k$ gibt. Der Beweis verläuft in zwei Schritten:

  1. Existenz für $n=p$: Es ist ein zentraler Satz der Algebra, dass die multiplikative Gruppe eines endlichen Körpers zyklisch ist. Da $\mathbb{Z}/p\mathbb{Z}$ ein endlicher Körper ist, ist die Gruppe $(\mathbb{Z}/p\mathbb{Z})^\ast$ zyklisch. Es gibt also eine Primitivwurzel modulo $p$.
  2. "Hochheben" von $p$ auf $p^k$: Man kann zeigen, dass eine Primitivwurzel $g$ modulo $p$ (mit einer kleinen Modifikation, falls nötig) auch eine Primitivwurzel modulo $p^k$ für alle $k \ge 1$ ist. Genauer gesagt: Wenn $g$ eine Primitivwurzel modulo $p$ ist, dann ist entweder $g$ oder $g+p$ eine Primitivwurzel modulo $p^2$ und damit auch für alle höheren Potenzen $p^k$. Da es einen Erzeuger (eine Primitivwurzel) gibt, ist die Gruppe $(\mathbb{Z}/p^k\mathbb{Z})^\ast$ zyklisch.

• Fall $n=2p^k$ ($p$ ungerade Primzahl, $k \ge 1$): Wir verwenden wieder den Chinesischen Restsatz: $(\mathbb{Z}/2p^k\mathbb{Z})^\ast \cong (\mathbb{Z}/2\mathbb{Z})^\ast \times (\mathbb{Z}/p^k\mathbb{Z})^\ast$ Die Gruppe $(\mathbb{Z}/2\mathbb{Z})^\ast = \{1\}$ ist die triviale Gruppe mit Ordnung 1. Das direkte Produkt mit einer trivialen Gruppe ändert die Struktur nicht, d.h.: $(\mathbb{Z}/2p^k\mathbb{Z})^\ast \cong (\mathbb{Z}/p^k\mathbb{Z})^\ast$ Da wir im vorherigen Schritt gezeigt haben, dass $(\mathbb{Z}/p^k\mathbb{Z})^\ast$ zyklisch ist, muss auch $(\mathbb{Z}/2p^k\mathbb{Z})^\ast$ zyklisch sein.

Der Beweis ist konstruktiv, das heisst, wir zeigen nicht nur die Existenz einer Lösung, sondern geben auch ein Verfahren an, um sie zu finden. Der Beweis besteht aus zwei Teilen: Existenz und Eindeutigkeit.

Teil 1: Existenz einer Lösung

1. Definition der Hilfsgrössen: Sei $N = n_1 \cdot n_2 \cdot \ldots \cdot n_k$ das Produkt aller Moduln. Für jedes $i \in \{1, 2, \dots, k\}$ definieren wir $N_i = \frac{N}{n_i}$. $N_i$ ist also das Produkt aller Moduln ausser $n_i$.

2. Teilerfremdheit: Da alle $n_j$ paarweise teilerfremd sind, ist $n_i$ teilerfremd zu jedem der Faktoren in $N_i$. Folglich gilt: $\text{ggT}(N_i, n_i) = 1$

3. Existenz des modularen Inversen: Weil $N_i$ und $n_i$ teilerfremd sind, existiert nach dem erweiterten Euklidischen Algorithmus ein modulares Inverses von $N_i$ bezüglich des Moduls $n_i$. Wir nennen dieses Inverse $y_i$. Es gilt also: $N_i \cdot y_i \equiv 1 \pmod{n_i}$

4. Konstruktion der Lösung: Wir konstruieren nun eine Lösung $x$ als eine Summe von Termen, die geschickt so gebaut sind, dass sie die meisten Kongruenzen trivial erfüllen. Sei: $x = a_1 N_1 y_1 + a_2 N_2 y_2 + \dots + a_k N_k y_k = \sum_{i=1}^k a_i N_i y_i$

5. Verifikation der Lösung: Wir müssen zeigen, dass dieses $x$ tatsächlich alle Kongruenzen erfüllt. Betrachten wir die $j$-te Kongruenz $x \equiv a_j \pmod{n_j}$: $x = \sum_{i=1}^k a_i N_i y_i \pmod{n_j}$ Wir teilen die Summe in zwei Teile auf: den Term für $i=j$ und alle anderen Terme für $i \neq j$.

   • Fall $i \neq j$: Per Definition ist $N_i$ das Produkt aller $n_m$ ausser $n_i$. Da $i \neq j$, ist der Faktor $n_j$ in diesem Produkt enthalten. Also ist $N_i$ ein Vielfaches von $n_j$, was bedeutet: $N_i \equiv 0 \pmod{n_j} \quad \text{für } i \neq j$ Daher fallen alle Terme $a_i N_i y_i$ für $i \neq j$ in der Kongruenz modulo $n_j$ weg.

   • Fall $i=j$: Der einzige verbleibende Term ist $a_j N_j y_j$. Wir wissen aus Schritt 3, dass $N_j y_j \equiv 1 \pmod{n_j}$.

   Setzen wir dies zusammen, erhalten wir: $x \equiv 0 + \dots + 0 + a_j(N_j y_j) + 0 + \dots + 0 \equiv a_j \cdot 1 \equiv a_j \pmod{n_j}$ Da dies für jedes beliebige $j \in \{1, \dots, k\}$ gilt, erfüllt unser konstruiertes $x$ alle Kongruenzen. Damit ist die Existenz einer Lösung bewiesen.

Teil 2: Eindeutigkeit der Lösung (modulo N)

Angenommen, wir haben zwei Lösungen, $x$ und $x'$. Wir müssen zeigen, dass sie kongruent modulo $N$ sind. Für jede der beiden Lösungen gilt per Definition für jedes $i \in \{1, \dots, k\}$: $x \equiv a_i \pmod{n_i} \quad \text{und} \quad x' \equiv a_i \pmod{n_i}$ Daraus folgt durch Subtraktion: $x - x' \equiv a_i - a_i \equiv 0 \pmod{n_i}$ Das bedeutet, $x-x'$ ist ein Vielfaches von $n_i$ für jedes $i$. Mit anderen Worten: $n_1 | (x-x')$, $n_2 | (x-x')$, ..., $n_k | (x-x')$.

Da die Zahlen $n_1, n_2, \dots, n_k$ paarweise teilerfremd sind, muss auch ihr Produkt $N = n_1 n_2 \dots n_k$ die Differenz $x-x'$ teilen. Also gilt: $N | (x-x')$ Dies ist äquivalent zu der Aussage: $x \equiv x' \pmod{N}$ Die Lösung ist also eindeutig bis auf Vielfache von $N$. Damit ist der Beweis vollständig.

Dieser Beweis ist ein klassisches und elegantes Resultat der Algebra.

Sei $F$ ein endlicher Körper und sei $m = |F^\ast| = |F|-1$ die Ordnung der multiplikativen Gruppe. Wir wollen zeigen, dass es ein Element $g \in F^\ast$ gibt, dessen Ordnung $\text{ord}(g) = m$ ist. Ein solches Element ist per Definition ein Erzeuger, und seine Existenz beweist, dass die Gruppe zyklisch ist.

Der Beweis stützt sich auf zwei Hauptpfeiler:

1. Die Anzahl der Wurzeln eines Polynoms über einem Körper.
2. Eine Eigenschaft der Eulerschen Phi-Funktion.

Beweisschritte:

1. Definition der Zählfunktionen: Für jeden Teiler $d$ von $m$, definieren wir zwei Mengen:

   • Sei $\psi(d)$ die Anzahl der Elemente in $F^\ast$ mit der exakten Ordnung $d$.
   • Sei $\varphi(d)$ der Wert der Eulerschen Phi-Funktion, der die Anzahl der ganzen Zahlen $k$ mit $1 \le k \le d$ und $\text{ggT}(k,d)=1$ angibt.

   Unser Ziel ist es zu zeigen, dass $\psi(m) > 0$ ist, denn das bedeutet, es gibt mindestens ein Element der Ordnung $m$.

2. Grundlegende Summenidentitäten: Jedes Element in der Gruppe $F^\ast$ hat eine Ordnung, die ein Teiler der Gruppenordnung $m$ ist (Satz von Lagrange). Wenn wir also die Anzahlen der Elemente für jede mögliche Ordnung summieren, erhalten wir die Gesamtanzahl der Elemente: $\sum_{d|m} \psi(d) = m$ Aus der Zahlentheorie ist eine fundamentale Eigenschaft der Phi-Funktion bekannt (Satz von Gauss für die Phi-Funktion): $\sum_{d|m} \varphi(d) = m$

3. Vergleich von $\psi(d)$ und $\varphi(d)$: Der Kern des Beweises ist zu zeigen, dass für jeden Teiler $d$ von $m$ gilt: $\psi(d) \le \varphi(d)$.

   • Fall 1: Es gibt kein Element der Ordnung $d$. In diesem Fall ist $\psi(d) = 0$. Da $\varphi(d) \ge 1$ für $d \ge 1$ ist, gilt trivialerweise $\psi(d) \le \varphi(d)$.
   • Fall 2: Es gibt mindestens ein Element der Ordnung $d$. Sei $a \in F^\ast$ ein solches Element mit $\text{ord}(a)=d$. Die Potenzen von $a$, also die Menge $C_d = \{a, a^2, \dots, a^d=1\}$, bilden eine zyklische Untergruppe der Ordnung $d$. Jedes dieser $d$ Elemente erfüllt die Gleichung $x^d - 1 = 0$. Über einem Körper kann ein Polynom vom Grad $d$ höchstens $d$ verschiedene Wurzeln haben. Das bedeutet, die Elemente von $C_d$ sind alle Wurzeln von $x^d-1$ in $F$. Jedes andere Element $b \in F^\ast$ mit der Ordnung $d$ muss ebenfalls die Gleichung $b^d=1$ erfüllen und somit eine Wurzel von $x^d-1$ sein. Daraus folgt, dass $b$ in der Untergruppe $C_d$ liegen muss. Die Frage "Wie viele Elemente haben die Ordnung $d$?" ist also gleichbedeutend mit "Wie viele Elemente in der zyklischen Gruppe $C_d$ haben die Ordnung $d$?" Ein Element $a^k \in C_d$ hat genau dann die Ordnung $d$, wenn $\text{ggT}(k,d)=1$. Die Anzahl dieser Elemente ist per Definition genau $\varphi(d)$. Also, wenn $\psi(d) > 0$, dann muss $\psi(d) = \varphi(d)$ sein.

   In beiden Fällen gilt also die Ungleichung $\psi(d) \le \varphi(d)$ für alle Teiler $d$ von $m$.

4. Schlussfolgerung: Wir haben zwei Summen, die beide über alle Teiler $d$ von $m$ laufen und beide denselben Wert $m$ ergeben: $\sum_{d|m} \psi(d) = m \quad \text{und} \quad \sum_{d|m} \varphi(d) = m$ Zudem wissen wir, dass für jeden einzelnen Summanden $\psi(d) \le \varphi(d)$ gilt. Wenn in zwei Summen mit lauter nicht-negativen Termen jeder Term der einen Summe kleiner oder gleich dem entsprechenden Term der anderen ist, die Summen aber gleich sind, dann müssen alle Terme paarweise gleich sein. Es muss also für alle $d|m$ gelten: $\psi(d) = \varphi(d)$ Insbesondere gilt dies für $d=m$: $\psi(m) = \varphi(m)$ Da $m = |F|-1 \ge 1$ ist (für $|F| \ge 2$), ist $\varphi(m) \ge 1$. Somit ist $\psi(m) \ge 1$, was bedeutet, dass es mindestens ein Element mit der Ordnung $m$ in $F^\times$ gibt. Die Gruppe ist also zyklisch.

Um zu beweisen, dass die Ordnung von $h^k$ einem bestimmten Wert $t$ entspricht, müssen wir zwei Dinge zeigen:

1. $(h^k)^t = e$ (wobei $e$ das neutrale Element der Gruppe ist).
2. $t$ ist die kleinste positive ganze Zahl mit dieser Eigenschaft.

1. Definition der Hilfsgrössen

Sei $d = \text{ggT}(k, m)$. Per Definition des ggT können wir $k$ und $m$ schreiben als:

• $k = d \cdot k'$
• $m = d \cdot m'$ wobei $k'$ und $m'$ teilerfremd sind, d.h. $\text{ggT}(k', m') = 1$.

Unser Ziel ist es zu zeigen, dass die Ordnung von $h^k$ genau $m' = \frac{m}{d}$ ist.

2. Nachweis, dass $(h^k)^{m'} = e$ ist

Wir potenzieren das Element $h^k$ mit $m'$:

Nun setzen wir die oben definierten Hilfsgrössen ein: $k=dk'$ und $m'=m/d$.

Wir können den Exponenten umformen zu:

Da die Ordnung von $h$ per Voraussetzung $m$ ist, gilt $h^m = e$. Also:

Damit haben wir gezeigt, dass die Ordnung von $h^k$ ein Teiler von $m'$ sein muss. $\text{ord}(h^k) \le m'$.

3. Nachweis, dass $m'$ die kleinste positive Potenz ist

Sei $j$ eine beliebige positive ganze Zahl, für die $(h^k)^j = e$ gilt. Wir müssen zeigen, dass $m'$ ein Teiler von $j$ ist. Dies beweist, dass $m'$ der kleinstmögliche Wert ist.

Aus $(h^k)^j = e$ folgt $h^{kj} = e$. Da die Ordnung von $h$ genau $m$ ist, muss der Exponent $kj$ ein Vielfaches von $m$ sein. Es gilt also:

Wir setzen wieder unsere Hilfsgrössen $m=dm'$ und $k=dk'$ ein:

Wir können auf beiden Seiten durch $d$ kürzen:

Nun kommt die entscheidende Eigenschaft der Teilerfremdheit ins Spiel. Wir wissen, dass $\text{ggT}(m', k') = 1$. Da $m'$ das Produkt $k'j$ teilt und zu $k'$ teilerfremd ist, muss $m'$ den anderen Faktor $j$ teilen (dies ist eine Folgerung aus dem Lemma von Euklid).

Dies zeigt, dass jede Potenz $j$, die $h^k$ zum neutralen Element macht, ein Vielfaches von $m'$ sein muss. Die kleinste positive solche Zahl ist daher $m'$ selbst.

Schlussfolgerung

Aus den Schritten 2 und 3 folgt, dass die Ordnung von $h^k$ exakt $m'$ ist: