Prime Restklassengruppe

Bezeichnet ${\displaystyle v_{p}}$ die ${\displaystyle p}$-Bewertung von ${\displaystyle n}$ (die Vielfachheit des Primfaktors ${\displaystyle p}$ in ${\displaystyle n}$), ist also

${\displaystyle n=\prod _{p}p^{v_{p}}}$

die Primfaktorzerlegung von ${\displaystyle n}$, dann gilt:

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \prod _{p}(\mathbb {Z} /p^{v_{p}}\mathbb {Z} )^{\times }}$

${\displaystyle {}\cong {\begin{cases}\mathbb {Z} /2\mathbb {Z} \;\times \;\mathbb {Z} /2^{v_{2}-2}\mathbb {Z} \;\times \;\prod _{p\neq 2}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {falls} \ 8\mid n\\\prod _{p}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {sonst} .\end{cases}}}$

oder mithilfe von ${\displaystyle \varphi }$ und der Schreibweise ${\displaystyle C_{n}}$ für eine zyklische Gruppe ausgedrückt:

${\displaystyle {}\cong {\begin{cases}C_{2}\;\times \;C_{2^{v_{2}-2}}\;\times \;\prod _{p\neq 2}C_{\varphi (p^{v_{p}})}&\mathrm {falls} \ 8\mid n\\\prod _{p}C_{\varphi (p^{v_{p}})}&\mathrm {sonst} .\end{cases}}}$

Die erste Isomorphieaussage (Zerlegung des Moduls ${\displaystyle n}$ in seine Primfaktoren) folgt aus dem chinesischen Restsatz. Die zweite Isomorphieaussage (Struktur der primen Restklassengruppe modulo Primzahlpotenz) folgt aus der Existenz gewisser Primitivwurzeln[1] (siehe auch den zugehörigen Hauptartikel Primitivwurzel).

Beachte: Mit den Gruppen ohne hochgestelltes ${\displaystyle \times }$ sind die additiven Gruppen ${\displaystyle \mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} }$ etc. gemeint!

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ist genau dann zyklisch, wenn ${\displaystyle n}$ gleich ${\displaystyle 1,2,4,p^{r}}$ oder ${\displaystyle 2p^{r}}$ ist mit einer ungeraden Primzahl ${\displaystyle p}$ und einer positiven Ganzzahl ${\displaystyle r}$. Genau dann existieren auch Primitivwurzeln modulo ${\displaystyle n}$, also Ganzzahlen ${\displaystyle a}$, deren Restklasse ${\displaystyle a+n\mathbb {Z} }$ ein Erzeuger von ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ist.

Wenn ${\displaystyle n=p}$ eine Primzahl ist, wird für den (genau dann) ausgebildeten Körper (engl. Field) ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )}$ meist ${\displaystyle \mathbb {F} _{p}}$ geschrieben; es ist dann ${\displaystyle \mathbb {F} _{p}^{\times }=\mathbb {F} _{p}\setminus \{{\bar {0}}\}}$; insbesondere ist die Gruppenordnung ${\displaystyle \#\mathbb {F} _{p}^{\times }=\varphi (p)=p-1}$.

Zu jeder primen Restklasse ${\displaystyle a+n\mathbb {Z} }$ existiert eine prime Restklasse ${\displaystyle b+n\mathbb {Z} }$, sodass gilt:

${\displaystyle ab\equiv 1{\pmod {n}}}$

Die prime Restklasse ${\displaystyle b+n\mathbb {Z} }$ ist also das inverse Element zu ${\displaystyle a+n\mathbb {Z} }$ bezüglich der Multiplikation in der primen Restklassengruppe ${\displaystyle \mathbb {Z} _{n}^{*}}$. Ein Repräsentant von ${\displaystyle b+n\mathbb {Z} }$ lässt sich mit Hilfe des erweiterten euklidischen Algorithmus bestimmen. Der Algorithmus wird auf ${\displaystyle a}$ und ${\displaystyle n}$ angewendet und liefert ganze Zahlen ${\displaystyle s}$ und ${\displaystyle t}$, die folgende Gleichung erfüllen:

${\displaystyle \operatorname {ggT} (a,n)=1=s\cdot a+t\cdot n}$.

Daraus folgt ${\displaystyle 1\equiv sa{\pmod {n}}}$, das heißt, ${\displaystyle s}$ ist ein Repräsentant der zu ${\displaystyle a+n\mathbb {Z} }$ multiplikativ inversen Restklasse ${\displaystyle b+n\mathbb {Z} }$.

Die Disquisitiones Arithmeticae wurden von Carl Friedrich Gauß auf Latein veröffentlicht. Die zeitgenössische deutsche Übersetzung umfasst alle seine Schriften zur Zahlentheorie:

• Carl Friedrich Gauß: Untersuchungen über höhere Arithmetik (deutsche Übersetzung), Original: Leipzig 1801.

• Armin Leutbecher: Zahlentheorie – Eine Einführung in die Algebra. 1. Auflage. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8.

1. A. Leutbecher: Zahlentheorie - Eine Einführung in die Algebra, S. 53–54.