Restklassenring (Z)/mod 23/Primitive Elemente/Beispiel

Wir betrachten die Einheitengruppe des Restklassenkörpers ${}\mathbb {Z} /(23)$. Nach Fakt ist sie zyklisch und es gibt daher Erzeuger der Einheitengruppe, also primitive Elemente. Wie kann man diese finden? Man ist hierbei prinzipiell auf Probieren angewiesen, man kann dies allerdings deutlich vereinfachen. Man weiß, dass die Einheitengruppe ${}22$ Elemente besitzt, als Ordnung von Elementen dieser Gruppe kommen also nur ${}1,2,11$ und ${}22$ in Frage. Es gibt genau ein Element mit der Ordnung ${}1$, nämlich ${}1$, und ein Element mit der Ordnung ${}2$, nämlich ${}-1=22$. Alle anderen Elemente haben also die Ordnung ${}11$ oder ${}22$, und genau die letzteren sind primitiv. Der erste Kandidat ist ${}2$. Wir müssen also

$2^{11}\mod 23$

ausrechnen. Es ist ${}2^{5}=32=9$ und daher ist

${}2^{11}=9\cdot 9\cdot 2=12\cdot 2=24=1\,.$

Die Ordnung ist also ${}11$, und die ${}2$ ist nicht primitiv. Betrachten wir die ${}3$. Es ist ${}3^{3}=27=4$ und daher ist

${}3^{11}=4\cdot 4\cdot 4\cdot 9=18\cdot 9=162=1\,,$

also wieder nicht primitiv. Der nächste Kandidat ${}4$ muss nicht gecheckt werden, denn wegen ${}4=2^{2}$ ist sofort ${}4^{11}=2^{22}=1$ (diese Beobachtung gilt für alle Quadratzahlen, und zwar auch für diejenigen Zahlen, die nur modulo ${}23$ ein Quadrat sind). Betrachten wir also ${}5$. Es ist ${}5^{2}=2$. Damit ist

${}5^{11}=2^{5}\cdot 5=9\cdot 5=45=-1\neq 1\,.$

Daher hat ${}5$ die Ordnung ${}22$ und ist ein primitives Element.

Man kann diesen Sachverhalt auch so ausdrücken, dass die Abbildung

$\mathbb {Z} /(22)\longrightarrow {\left(\mathbb {Z} /(23)\right)}^{\times },\,k\longmapsto 5^{k},$

einen Gruppenisomorphismus definiert. Dieser übersetzt die Addition in die Multiplikation, daher spricht man von einer diskreten Exponentialfunktion und nennt die Umkehrabbildung auch einen diskreten Logarithmus. Solche Abbildungen spielen eine wichtige Rolle in der Kryptologie. Wenn man wie in diesem Beispiel einen solchen Isomorphismus gefunden hat, so kann man viele Eigenschaften der Einheitengruppe in der „einfacheren“ Gruppe entscheiden. Z.B. sind in ${}\mathbb {Z} /(22)$ alle ungeraden Elemente außer ${}11$ ein Gruppenerzeuger, daher sind in der Einheitengruppe alle Elemente der Form

$5^{u},u{\text{ ungerade}},u\neq 11,$

primitiv.