Restklassenringe (Z)/mod 31/Primitive Elemente und Quadrate/Aufgabe/Lösung

Es gibt $16$ Quadrate. $\phi (30)=\phi (2\cdot 3\cdot 5)=2\cdot 4=8$, also gibt es $8$ primitive Elemente.

Ein Quadrat ist nicht primitiv. Deshalb gibt es $8+16=24$ Elemente, die ein Quadrat oder primitiv sind. Es verbleiben $7$ Elemente, die weder ein Quadrat noch primitiv sind.

Es sei $x$ primitiv. Ein Element der Form $x^i$ ist genau dann primitiv, wenn $i$ und $30$ teilerfremd sind. Es ist genau dann ein Quadrat, wenn $i$ gerade ist. Gesucht sind also die ungeraden Zahlen $\le 30$, die nicht teilerfremd zu $30$ sind. Sie müssen also $3$ oder $5$ als Teiler haben. Damit verbleiben $i=3,5,9,15,21,25,27$.

Zur gelösten Aufgabe