Wie viele Primitivwurzeln gibt es Modulo 20?

Question

Aufgabe:

1. Wie viele Primitivwurzeln gibt es Modulo 20?

2. Wie viele Primitivwurzeln gibt es Modulo 18?

Problem/Ansatz:

Wieso ist es bei 20 die 8 keine Primitivwurzel und wieso rechnet man bei Modulo 18 mit Phi von 6 weiter ?

Text erkannt:

$\begin{aligned} \varphi(20) & =\varphi(2) \cdot \varphi(10) \\ & =\varphi(2) \cdot \varphi(2) \cdot \varphi(5) \\ & =\left(2^{2}-21\right) \cdot\left(5^{2}-5^{0}\right) \\ & =8 \end{aligned}$
$=8 \rightarrow \text { es jitl have pW noduro } 20$
$\begin{aligned} \varphi(11) & =\varphi(2) \cdot \varphi(5) \\ & =\varphi(2) \cdot \varphi(3) \cdot \varphi(3) \\ & =\varphi(2) \cdot \varphi\left(3^{2}\right) \\ & =\left(3^{2}-3^{1}\right) \cdot\left(2^{1}-2^{0}\right) \\ & =6 \end{aligned}$
dann
$\begin{aligned} y(6) & =\varphi(3) \cdot \varphi(2) \\ & =\left(3^{1}-3^{0}\right) \cdot\left(2^{1}-2^{0}\right) \end{aligned}$
$=2^{L}, 0$ jett 270 module $18 \%$

Comments

Es gibt keine Primitivwurzel modulo $20$.
Es gibt $\varphi\big(\varphi(18)\big)=\varphi(6)=2$ Primitivwurzeln modulo $18$. Diese sind $5$ und $11$.
Vgl. https://de.wikipedia.org/wiki/Primitivwurzel
oder auch https://www.wolframalpha.com/input?i=primitive+roots%2818%29.

Answer 1

Merksatz:

Wenn es Primitivwurzeln modulo m gibt, dann gibt es φ(φ(m)) Primitivwurzeln

Wie du hier ohne einen Test feststellst das es bei φ(20) = 8 keine Primitivwurzeln und bei φ(18) = 6 Primitivwurzeln gibt entzieht sich mir allerdings der Kenntnis. Normal müsstest du die möglichen Primitivwurzeln testen bis du zumindest eine findest.

Nur wenn m in modulo m eine Primzahl ist, dann gibt es garantiert eine Primitivwurzel und damit kennst du dann auch die Anzahl.

Comments

Könntest du ein Beispiel mit zahlen machen wie man das testet und zum Entschluss kommt das es keine Primitivwurzel gibt zum Beispiel bei Phi von 20 = 8 ?

---

Da

φ(20) = 8 : {1, 3, 7, 9, 11, 13, 17, 19}

brauchen wir uns nur die Potenzen von 3, 7, 9, 11, 13, 17 und 19 anzusehen.

3⁴ ≡ 1
7⁴ ≡ 1
9⁴ ≡ 1
11⁴ ≡ 1
13⁴ ≡ 1
17⁴ ≡ 1
19⁴ ≡ 1

Damit haben alle Zahlen höchstens die Ordnung 4 und können daher keine Primitivwurzeln sein.

Answer 2

Aus Bequemlichkeitsgründen schreibe ich $Z$ statt $\mathbb{Z}$.

Ferner lasse ich die Restklassen von $Z/nZ$ durch Repräsentanten

vertreten. Nach dem chinesischen Restsatz gilt

$Z/20Z\cong Z/5Z\times Z/4Z$ und $Z/18Z\cong Z/2Z\times Z/9Z$.

Für die Einheitengruppen dieser Ringe gilt dann

$G_1=(Z/20Z)^*\cong (Z/5Z)^*\times (Z/4Z)^*$ und

$G_2=(Z/18Z)^*\cong (Z/2Z)^*\times (Z/9Z)^*$,

also

$(Z/20Z)^*\cong\{1,2,3,4\}\times \{1,3\}$ und

$(Z/18Z)^*\cong \{1\}\times \{1,2,4,5,7,8\}$

Da alle Elemente von $G_1$ höchstens die Ordnung 4 haben,

ist $G_1$ nicht zyklisch, besitzt also keine

Primitivwurzel.

$G_2$ besitzt die Primitivwurzel $r=(1,2)$.

Die Primitivwurzeln sind dann

$r^1, r^5$, da die zu $6=|\{1,2,4,5,7,8\}|$ teilerfremden Zahlen 1,5 sind.