imported>Engcobo am 23. März 2026 um 21:28 Uhr

2026-03-23T21:28:31Z

Neue Seite

Die '''prime Restklassengruppe''' ist die [[Gruppe (Mathematik)|Gruppe]] der [[Restklassenring#Invertierbarkeit und Inversenberechnung|primen Restklassen]] bezüglich eines Moduls <math>n</math>. Das ist zugleich die [[Einheitengruppe|Gruppe der Einheiten]] des [[Restklassenring]]s <math>\Z/n\Z</math> (die daher oft als <math>(\Z/n\Z)^\times</math> oder <math>\Z_n^*</math> notiert wird). Denn die [[Teilerfremdheit|primen]] [[Restklasse]]n sind genau die multiplikativ invertierbaren Elemente im Restklassenring. Die primen Restklassengruppen sind endliche [[abelsche Gruppe]]n bezüglich der [[Multiplikation]]. Sie spielen in der [[Kryptographie]] eine bedeutende Rolle.

Die Gruppe besteht aus den Restklassen <math>a + n\Z</math>, deren Elemente zu <math>n</math> [[teilerfremd]] sind. Gleichwertig dazu muss für den Repräsentanten <math>a</math> der Restklasse <math>\operatorname{ggT}(a,n) = 1</math> gelten, wobei ggT den [[Größter gemeinsamer Teiler|größten gemeinsamen Teiler]] bezeichnet. Darauf weist die Bezeichnung „''prime'' Restklasse“ hin, für ''teilerfremd'' sagt man auch ''relativ prim''. Die [[Gruppenordnung]] von <math>\Z_n^*</math> ist durch den Wert <math>\varphi(n)</math> der [[Eulersche φ-Funktion|eulerschen φ-Funktion]] gegeben.

== Struktur ==
Bezeichnet <math>v_p</math> die <math>p</math>-[[Bewertungstheorie|Bewertung]] von <math>n</math> (die Vielfachheit des Primfaktors <math>p</math> in <math>n</math>), ist also
: <math>n = \prod_p p^{v_p}</math>
die [[Primfaktorzerlegung]] von <math>n</math>, dann gilt:
: <math>(\Z/n\Z)^\times \cong \prod_p(\Z/p^{v_p}\Z)^\times</math>
:: <math>{}\cong\begin{cases}\Z/2\Z \; \times \; \Z/2^{v_2-2}\Z \; \times \; \prod_{p \neq 2}\Z/(p-1)p^{v_p-1}\Z&\mathrm{falls}\ 8 \mid n\\ \prod_p\Z/(p-1)p^{v_p-1}\Z&\mathrm{sonst}\end{cases}</math>
:: oder mithilfe von <math>\varphi</math> und der Schreibweise <math>C_n</math> für die [[zyklische Gruppe]] der Ordnung <math>n</math> ausgedrückt:
:: <math>{}\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_pC_{\varphi(p^{v_p})}&\mathrm{sonst}\end{cases}</math>

Die erste Isomorphieaussage (Zerlegung des Moduls <math>n</math> in seine Primfaktoren) folgt aus dem [[Chinesischer Restsatz|chinesischen Restsatz]]. Die zweite Isomorphieaussage (Struktur der primen Restklassengruppe modulo Primzahlpotenz) folgt aus der Existenz gewisser [[Primitivwurzel]]n.<ref name="Leutbecher">A. Leutbecher: ''Zahlentheorie – Eine Einführung in die Algebra'', S. 53–54.</ref>

Beachte: Mit den Gruppen ohne hochgestelltes <math>\times</math> sind die ''additiven'' Gruppen <math>\Z/(p-1)p^{v_p-1}\Z</math> etc. gemeint.

<math>(\Z/n\Z)^\times</math> ist genau dann [[Zyklische Gruppe|zyklisch]], wenn <math>n</math> gleich <math>1, 2, 4, p^r</math> oder <math>2p^r</math> ist mit einer ungeraden [[Primzahl]] <math>p</math> und einer positiven Ganzzahl <math>r</math>. Genau dann existieren auch [[Primitivwurzel]]n modulo <math>n</math>, also Ganzzahlen <math>a</math>, deren Restklasse <math>a + n \Z</math> ein [[Erzeuger (Algebra)|Erzeuger]] von <math>(\Z/n\Z)^\times</math> ist.

== Sonderfall: Modul ist Primzahl ==
Wenn <math>n = p</math> eine Primzahl ist, wird für den (genau dann) ausgebildeten [[Körper (Algebra)|Körper]] (engl. Field) <math>(\Z/p\Z)</math> meist <math>\mathbb F_p</math> geschrieben. Es ist dann <math>\mathbb F^\times_p = \mathbb F_p \setminus \{\bar 0\}</math>, insbesondere ist die Gruppenordnung <math>\# \mathbb F^\times_p = \varphi(p) = p-1</math>.

== Berechnung der inversen Elemente ==
Zu jeder primen Restklasse <math>a + n \Z</math> existiert eine prime Restklasse <math>b + n \Z</math>, sodass gilt:
:<math>ab \equiv 1 \pmod n</math>

Die prime Restklasse <math>b + n \Z</math> ist also das inverse Element zu <math>a + n \Z</math> bezüglich der Multiplikation in der primen Restklassengruppe <math>\Z_n^*</math>. Ein Repräsentant von <math>b + n \Z</math> lässt sich mit Hilfe des [[Erweiterter Euklidischer Algorithmus|erweiterten euklidischen Algorithmus]] bestimmen. Der Algorithmus wird auf <math>a</math> und <math>n</math> angewendet und liefert ganze Zahlen <math>s</math> und <math>t</math>, die folgende Gleichung erfüllen:
:<math>\operatorname{ggT}(a,n) = 1 = s \cdot a + t \cdot n</math>
Daraus folgt <math>1 \equiv sa \pmod n</math>, das heißt, <math>s</math> ist ein Repräsentant der zu <math>a + n \Z</math> multiplikativ inversen Restklasse <math>b + n \Z</math>. Ein Beispiel dazu findet man im Artikel [[Restklassenring#Invertierbarkeit und Inversenberechnung|Restklassenring]].

== Literatur ==
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ß]]: ''[https://gdz.sub.uni-goettingen.de/id/PPN373456743 Untersuchungen über höhere Arithmetik]'' (deutsche Übersetzung), Original: Leipzig 1801.
* Armin Leutbecher: ''Zahlentheorie – Eine Einführung in die Algebra''. 1. Auflage. Springer Verlag, Berlin / Heidelberg / New York 1996. ISBN 3-540-58791-8.

== Einzelnachweise ==
<references />

[[Kategorie:Zahlentheorie]]

Prime Restklassengruppe - Versionsgeschichte

imported>Engcobo am 23. März 2026 um 21:28 Uhr