Primitivwurzeln

Jetzt soll es um die Restklassengruppen $\langle \mathbb{Z}_n^* \mid \,\cdot\,\rangle$ gehen. Sie sind Prototypen für zyklische Gruppen.

Strukturen Modulo 17 unter Multiplikation

Nimmt man für das Modul eine Primzahl, wird die Struktur praktikabel. Beispiele zur Modulo-Arithmetik: Modulo $17$ ist $13+8 = 21\equiv 4\mod 17$ oder $4-9 = -5\equiv12\mod17$ . Spannend ist auch die Multiplikation: $5\cdot4 = 20\equiv3\mod17$ und $9\cdot 2 = 18\equiv1\mod17$ . Die letzte Kongruenz besagt, dass $9$ das multiplikative Inverse von $2$ ist (Modulo $17$ ):

9\equiv \frac{1}{2} \mod 17.

(Potenzen Modulo 17 kommentiert)

Potenzen

Wir berechnen illustrativ alle Potenzen von $3$ Modulo $17$ .

Exercise 1: Potenzen von 3 Modulo 17

Vervollständige folgende Tabelle:

n	0	1	2	3	4	5	6	7
$3^n$	1	3	9	10

n	8	9	10	11	12	13	14	15
$3^n$

Solution

n	0	1	2	3	4	5	6	7
$3^n \pmod{17}$	1	3	9	10	13	5	15	11

n	8	9	10	11	12	13	14	15
$3^n \pmod{17}$	16	14	8	7	4	12	2	6

Es fällt auf, dass jede Zahl ungleich $0$ eine Potenz von $3$ ist; also jeder mögliche, nichttriviale Rest taucht genau einmal auf. Ausserdem stellt man fest:

3^{16}\equiv3\cdot6 = 18\equiv1\mod17.

Ausser $0$ sind alle Zahlen eine Potenz von $3$ und $3^{16}\equiv1\mod17$ impliziert: Jede Zahl $a\not\equiv0\mod17$ hat als $16$ -te Potenz den Wert $1$ ; denn $a$ ist eine Potenz von $3$ , also $a = 3^n$ und daher

a^{16} = (3^n)^{16} = (3^{16})^n\equiv1^n = 1\mod17

Das bedeutet, es gilt auch

a^{17} = a, a^{33} = a, a^{49} = a, \dots

und daraus erhält man

a = a^{33} = a^{3\cdot11} = (a^3)^{11}.

Note 1

Man zieht die dritte Wurzel, indem man mit $11$ potenziert.

Exercise 2: Modulo Wurzel

Ziehe durch Potenzieren die siebte Wurzel aus $a^7\mod17$ .

Solution

Es gilt für ein beliebiges Element $a\in\mathbb{Z}_{17}^\ast$ , dass $a^{16}\equiv1\mod{17}$ . Um die siebte Wurzel aus $a^7$ zu ziehen, suchen wir einen Exponenten $x$ , so dass $(a^7)^x \equiv a \mod 17$ . Das bedeutet $7x \equiv 1 \mod 16$ .

Wir erkennen, dass $x = 7$ eine Lösung ist, denn $7 \cdot 7 = 49$ . Da $49 = 3 \cdot 16 + 1$ , gilt $49 \equiv 1 \mod 16$ .

Also können wir rechnen: $(a^7)^7 = a^{49} = a^{3 \cdot 16 + 1} = (a^{16})^3 \cdot a^1 \equiv 1^3 \cdot a \equiv a \mod 17$ .

Man zieht die siebte Wurzel also, indem man mit $7$ potenziert.

Eine Idee zur Kryptogarphie

Kryptographie - eine erste Idee

Letztgenannte Beziehungen enthalten eine der Grundideen der Kryptologie basierend auf Zahlentheorie. Benutzt man die $16$ Zahlen von $1$ bis $16$ als verkürztes Alphabet, kann man eine gewählte Zahl als Verschlüsselungsexponent verwenden - beispielsweise $e = 3$ . Die Entschlüsselung erfolgt dann mittels Potenzierung mit dem entsprechenden Entschlüsselungsexponenten $d = 11$ - da $e \cdot d = 3 \cdot 11 = 33 \equiv 1 \pmod{16}$ .

Example 1

Wir wählen den Buchstaben c, der dem Wert $3$ entspricht (da a = 1, b = 2, c = 3). Mit dem Verschlüsselungsexponenten $e = 3$ verschlüsseln wir ihn: $3^3\equiv10\mod17$ . Der Chiffretext ist also $10$ , was dem Buchstaben K entspricht. Zur Entschlüsselung potenzieren wir den Chiffretext mit dem Entschlüsselungsexponenten $d = 11$ : $10^{11}\equiv3\mod17$ ; wir erhalten wieder den Klartext c.

Ein angenehmer Aspekt dieses Verfahrens ist, dass zur Ver- und Entschlüsselung dasselbe Rechenverfahren benutzt wird (Potenzierung) - und dass die Reihenfolge von Ver- und Entschlüsselung vertauscht werden kann. Dies eröffnet in der Kryptologie interessante Möglichkeiten. Wie praktisch das Verfahren ist, hängt nun davon ab, ob und wie leicht zum "Verschlüsselungsexponenten" $3$ der "Entschlüsselungsexponent" $11$ berechnet werden kann.

Definition 1: Primitivwurzel

Ein Element $a \in \mathbb{Z}_n^\ast$ heisst Primitivwurzel modulo $n$ , wenn die Potenzen $a^k$ mit $k \in \mathbb{N}$ sämtliche Reste in $\langle \mathbb{Z}_n^\ast\,,\,\cdot\,\rangle$ erzeugen.

Example 2

$2\in\mathbb{Z}^\ast_7$ ist keine Primitivwurzel, da $2^1\equiv2$ , $2^2\equiv4$ , $2^3\equiv1$ , $2^4\equiv2$ , .... Hingegen ist $3\in\mathbb{Z}^\ast_7$ Primitivwurzel: $3^1\equiv3$ , $3^2\equiv2$ , $3^3\equiv6$ , $3^4\equiv4$ , $3^5\equiv5$ , $3^6\equiv1$ .

Exercise 3: Primitivwurzeln in \langle\mathbb{Z}^*_{17},\cdot\rangle

Bestimme für $k\in\mathbb{N}$ in der Gruppe $\langle\mathbb{Z}^*_{17},\cdot\rangle$ die Werte der Potenzen $2^k$ und $3^k$ .

Solution

Sei $k\in\mathbb{N}$ . Betrachte folgende Tabelle:

$k$	1	2	3	4	5	6	7	8
$2^k \pmod{17}$	2	4	8	16	15	13	9	1
$3^k \pmod{17}$	3	9	10	13	5	15	11	16

$k$	9	10	11	12	13	14	15	16
$2^k \pmod{17}$	2	4	8	16	15	13	9	1
$3^k \pmod{17}$	14	8	7	4	12	2	6	1

Exercise 4: Zurück zur 1

Zeige: Sei $a\in\mathbb{Z}^*_{17}$ beliebig. Dann gilt $a^{16}\equiv1\mod17$ .

Solution

Aus der Tabelle lesen wir, dass für $a\in\langle\mathbb{Z}_{17}^*,\cdot\rangle$ beliebig es ein $k\in\mathbb{Z}$ gibt, so dass $3^k\equiv a$ . Es folgt

a^{16}\equiv(3^k)^{16}\equiv(3^{16})^k\equiv 1^k\equiv1.

Definition 2: Euler'sche phi-Funktion

Für $n\in\mathbb{N}$ ist die Euler'sche $\varphi$ -Funktion definiert durch

\varphi(n):=\text{card}(\{a\in\mathbb{N}\mid 1\leq a\leq n, \gcd(a,n)=1\}).

Exercise 5

Bestimmen Sie die Funktionswerte der Euler'schen $\varphi$ -Funktion für die Argumente

a) $6$

b) $10$

c) $11$

d) $51$

e) $p$ für $p\in\mathbb{N}$ prim

Solution

Die Euler'sche $\varphi$ -Funktion einer natürlichen Zahl $n\in\mathbb{N}$ zählt die Anzahl teilerfremden Zahlen zwischen und inklusive $1$ und $n$ . Im Folgenden werden also für $\varphi(n)$ immer natürliche Zahlen $k\in\mathbb{N}$ mit $1\leq k\leq n$ betrachtet.

a) $\varphi(6)=2$ , da $1$ und $5$ teilerfremd zu $6$ sind.

b) Wegen $10=2\cdot5$ sind $1$ , $3$ , $7$ und $9$ teilerfremd zu $10$ , also $\varphi(10)=4$ .

c) Primzahlen haben als grössten gemeinsamen Teiler ungleich $1$ nur sich selbst, d.h. $\varphi(11)=10$ .

d) $51=3\cdot 17$ und man kann die Multiplikativität $\varphi(3\cdot17)=\varphi(3)\cdot\varphi(17)$ der Euler'schen $\varphi$ -Funktion brauchen:

\varphi(3\cdot17)=\varphi(3)\cdot\varphi(17)=2\cdot16=32.

e) Ist $p$ prim, so hat $p$ per Definition nur die Teiler $1$ und sich selbst. Also ist für $k\in\mathbb{N}$ , $1\leq l\leq p$ , nur im Falle $l=p$ der $\gcd(l,p)=p$ , sonst immer $1$ . Das heisst es gilt $\varphi(p)=p-1$ .

Exercise 6: Multiplikativität für Primes

Seien $p,q\in\mathbb{P}$ , dann gilt

\varphi(p\cdot q) = \varphi(p)\cdot\varphi(q).

Solution

Da $p,q\in\mathbb{P}$ hat $p\cdot q$ sicher den (trivialen) Teiler $pq$ und ferner die Teiler $p$ , $2p$ , $\dots$ , $(q-1)p$ , sowie $q$ , $2q$ , $\dots$ , $(p-1)q$ . Für alle andern $1\le a\le pq$ ist $\operatorname{ggT}(pq,a)=1$ und das sind

pq-(p-1)-(q-1)-1 = pq-p-q+1 = (p-1)(q-1)

Stück.

Exercise 7: Suche Inverse

Welche Elemente $a\in\mathbb{Z}^*_{12}$ haben inverse Elemente in der Struktur $\langle\mathbb{Z}^*_{12},\cdot\rangle$ ?

Solution

Erwischt man einen Teiler, ausser $1$ , von $12$ , dann wird der Rest nie $1$ , das multiplikativ neutrale Element, betragen. Das heisst alle Elemente mit grösstem gemeinsamen Teiler $1$ zu $12$ werden ein inverses Element haben. Nämlich sind $1$ , $5$ , $7$ und $11$ alle zu sich selbst invers.

Theorem 1: Satz von Gauss über die Existenz von Primitivwurzeln in zyklischen Gruppen

Die prime Restklassengruppe $G = (\mathbb{Z}/n\mathbb{Z})^\ast$ ist genau dann zyklisch, wenn für $n$ einer der folgenden Werte gilt: $n = 1, 2, 4, p^k \text{ oder } 2p^k$ wobei $p$ eine ungerade Primzahl und $k \ge 1$ eine ganze Zahl ist.

Eine Primitivwurzel modulo $n$ existiert genau dann, wenn die Gruppe $(\mathbb{Z}/n\mathbb{Z})^\ast$ zyklisch ist.

Proof

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:

(\mathbb{Z}/n\mathbb{Z})^\ast \cong (\mathbb{Z}/2^k\mathbb{Z})^\ast \times (\mathbb{Z}/p_1^{k_1}\mathbb{Z})^\ast\times \cdots\times(\mathbb{Z}/p_r^{k_r}\mathbb{Z})^\ast

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\,| = \phi(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\,| = \phi(2^k) = 2^{k-1}$ (für $k \ge 1$ ).

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

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.
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 $\phi(2^k)=2^{k-1}$ (für $k \ge 2$ ) und $\phi(p^j)=p^{j-1}(p-1)$ . Wenn $k \ge 2$ , ist $\phi(2^k)=2^{k-1}$ gerade. Da $\phi(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$ ).
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^{\phi(2^k)/2} = a^{2^{k-2}} \equiv 1 \pmod{2^k}$ . Es gibt also kein Element der Ordnung $\phi(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.

Theorem 2: Primitivwurzelsatz von Euler

Wenn für einen Modul $n$ Primitivwurzeln existieren (d.h., wenn $(\mathbb{Z}/n\mathbb{Z})^\ast$ eine zyklische Gruppe ist), dann gibt es genau $\varphi(\varphi(n))$ inkongruente Primitivwurzeln modulo $n$ .

Ist ferner $g$ eine Primitivwurzel modulo $n$ , so ist die Menge aller (inkongruenten) Primitivwurzeln modulo $n$ gegeben durch die Menge:

\{ g^k \pmod{n} \mid 1 \le k < \varphi(n) \text{ und } \text{ggT}(k, \varphi(n)) = 1 \}

Proof

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:

\text{ord}(h^k) = \frac{m}{\text{ggT}(k,m)}

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:

\text{ord}_n(g^k) = \frac{\text{ord}_n(g)}{\text{ggT}(k, \text{ord}_n(g))} = \frac{\varphi(n)}{\text{ggT}(k, \varphi(n))}

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:

\text{ggT}(k,\varphi(n))=1

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.

Exercise 8: Primitivwurzeln von \langle\mathbb{Z}^*_{13},\cdot\rangle

Bestimme alle Primitivwurzeln der Gruppe $\langle\mathbb{Z}^*_{13},\cdot\rangle$ .

Solution

Nach Carl F. Gauss gibt es $\varphi(\varphi(13))=\varphi(12)=4$ Primitivwurzeln ( $\gcd$ $1$ haben die Werte $1$ , $5$ , $7$ und $11$ .). Nun suchen wir eine Primitivwurzel durch Ausprobieren: $2^1\equiv2$ , $2^2\equiv4$ , $2^3\equiv8$ , $2^4\equiv3$ , $2^5\equiv6$ , $2^6\equiv12$ , $2^7\equiv11$ , $2^8\equiv9$ , $2^9\equiv5$ , $2^{10}\equiv10$ , $2^{11}\equiv7$ , $2^{12}\equiv1$ ist also eine Primitivwurzel. Damit sind die Primitivwurzeln $2^1\equiv2$ , $2^5\equiv6$ , $2^7\equiv11$ und $2^{11}\equiv7$ .

Exercise 9: Primitivwurzeln von \langle\mathbb{Z}^*_{17},\cdot\rangle

Bestimmen Sie alle Primitivwurzeln der Gruppe $\langle\mathbb{Z}^*_{17},\cdot\rangle$ .

Solution

Es gibt $\varphi(\varphi(17))=\varphi(16)=8$ Primitivwurzeln ( $\gcd$ $1$ haben die Werte $1$ , $3$ , $5$ , $7$ , $9$ , $11$ , $13$ und $15$ .). Aus der Tabelle oben entnehmen wir, dass $2$ keine, dafür aber $3$ eine Primitwurzel ist. Also sind die Primitivwurzeln von $\mathbb{Z}^*_{17}$ : $3^1\equiv3$ , $3^3\equiv10$ , $3^5\equiv5$ , $3^7\equiv11$ , $3^9\equiv14$ , $3^{11}\equiv7$ , $3^{13}\equiv12$ und $3^{15}\equiv6$ .

Exercise 10: Primitivwurzeln von \langle\mathbb{Z}^*_{31},\cdot\rangle

Bestimmen Sie alle Primitivwurzeln der Gruppe $\langle\mathbb{Z}^*_{31},\cdot\rangle$ .

Solution

Hier haben wir $\varphi(\varphi(31))=\varphi(30)=8$ ( $1$ , $7$ , $11$ , $13$ , $17$ , $19$ , $23$ , $29$ ). $2$ ist wegen $2^5\equiv1$ keine Primitivwurzel. $3$ entpuppt sich als Primitivwurzel, und wir haben somit $3$ , $11$ , $12$ , $13$ , $17$ , $21$ , $22$ , $24$ als solche in $\mathbb{Z}_{31}^*$ .

Exercise 11: 🧩

Wie viele Primitivwurzeln hat die multiplikative Restklassengruppe $\langle \mathbb{Z}^*_{73},\cdot\rangle$ ?

Solution

Nach Gauss gibt es $\varphi(\varphi(73))$ Primitivwurzeln. Das sind

\varphi(\varphi(73))=\varphi(72)=72\cdot(1-\frac{1}{2})\cdot(1-\frac{1}{3})=72\cdot\frac{1}{3}=24