Menge der primen Restklassen

In mathbb{Z} 8 gibt es acht Klassen overline{0}, dots, overline{7} . Wer malnehmen und wieder rückgängig machen will, kann aber nur mit den Klassen arbeiten, die ein Inverses haben – das sind die Prime Restklassen|primen Restklassen overline{1}, overline{3}, overline{5}, overline{7} . Diese „guten“ Klassen fasst man zu einer eigenen Menge zusammen: der Menge der primen Restklassen . Darin kann man ohne Ausnahme malnehmen und „teilen“ – deshalb rechnen Verschlüsselungsverfahren wie RSA genau hier. Definition mathbb{Z} m^ = { overline{a} in mathbb{Z} m mid text{ggT}(a, m) = 1 } qquad text{(auch } R m^ text{)} Anzahl der Elemente: Das ist genau die Euler'sche Phi-Funktion : | mathbb{Z} m^ | = varphi(m) Gruppe: ( mathbb{Z} m^ , cdot) ist eine kommutative Gruppe : - abgeschlossen: Das Produkt zweier primer Restklassen ist wieder prim (wer mit m keinen Teiler gemeinsam hat, bekommt auch beim Malnehmen keinen dazu). - neutrales Element: overline{1} - Inverses: Jede Klasse hat eins – berechnet mit dem Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus . - Reihenfolge egal: overline{a} cdot overline{b} = overline{b} cdot overline{a} Sonderfall Primzahl: Ist m = p eine Primzahl, dann ist mathbb{Z} p^ = { overline{1}, overline{2}, dots, overline{p - 1} } und varphi(p) = p - 1 . Bestimme mathbb{Z} 8^ . 8 = 2^3 → prim sind die Klassen mit ungeradem Repräsentanten: mathbb{Z} 8^ = { overline{1}, overline{3}, overline{5}, overline{7} }, qquad varphi(8) = 4 Multiplikati

Worum geht's?

In Z 8 \mathbb{Z}_8 Z 8 ​ gibt es acht Klassen 0 ‾ , … , 7 ‾ \overline{0}, \dots, \overline{7} 0 , … , 7 . Wer malnehmen und wieder rückgängig machen will, kann aber nur mit den Klassen arbeiten, die ein Inverses haben – das sind die primen Restklassen 1 ‾ , 3 ‾ , 5 ‾ , 7 ‾ \overline{1}, \overline{3}, \overline{5}, \overline{7} 1 , 3 , 5 , 7 . Diese „guten“ Klassen fasst man zu einer eigenen Menge zusammen: der Menge der primen Restklassen . Darin kann man ohne Ausnahme malnehmen und „teilen“ – deshalb rechnen Verschlüsselungsverfahren wie RSA genau hier.

Formel mit Erklärung

Definition Z m ∗ = { a ‾ ∈ Z m ∣ ggT ( a , m ) = 1 } (auch  R m ∗ ) \mathbb{Z}_m^* = \{\overline{a} \in \mathbb{Z}_m \mid \text{ggT}(a, m) = 1\} \qquad \text{(auch } R_m^*\text{)} Z m ∗ ​ = { a ∈ Z m ​ ∣ ggT ( a , m ) = 1 } (auch  R m ∗ ​ ) Anzahl der Elemente: Das ist genau die Euler'sche Phi-Funktion : ∣ Z m ∗ ∣ = φ ( m ) |\mathbb{Z}_m^*| = \varphi(m) ∣ Z m ∗ ​ ∣ = φ ( m ) Gruppe: ( Z m ∗ , ⋅ ) (\mathbb{Z}_m^*, \cdot) ( Z m ∗ ​ , ⋅ ) ist eine kommutative Gruppe : abgeschlossen: Das Produkt zweier primer Restklassen ist wieder prim (wer mit m m m keinen Teiler gemeinsam hat, bekommt auch beim Malnehmen keinen dazu). neutrales Element: 1 ‾ \overline{1} 1 Inverses: Jede Klasse hat eins – berechnet mit dem erweiterten euklidischen Algorithmus . Reihenfolge egal: a ‾ ⋅ b ‾ = b ‾ ⋅ a ‾ \overline{a} \cdot \overline{b} = \overline{b} \cdot \overline{a} a ⋅ b = b ⋅ a Sonderfall Primzahl: Ist m = p m = p m = p eine Primzahl, dann ist Z p ∗ = { 1 ‾ , 2 ‾ , … , p − 1 ‾ } \mathbb{Z}_p^* = \{\overline{1}, \overline{2}, \dots, \overline{p - 1}\} Z p ∗ ​ = { 1 , 2 , … , p − 1 ​ } und φ ( p ) = p − 1 \varphi(p) = p - 1 φ ( p ) = p − 1 .

Beispiele

Leicht#1
Bestimme Z 8 ∗ \mathbb{Z}_8^* Z 8 ∗ ​ . 8 = 2 3 8 = 2^3 8 = 2 3 → prim sind die Klassen mit ungeradem Repräsentanten: Z 8 ∗ = { 1 ‾ , 3 ‾ , 5 ‾ , 7 ‾ } , φ ( 8 ) = 4 \mathbb{Z}_8^* = \{\overline{1}, \overline{3}, \overline{5}, \overline{7}\}, \qquad \varphi(8) = 4 Z 8 ∗ ​ = { 1 , 3 , 5 , 7 } , φ ( 8 ) = 4 Multiplikationstafel: ⋅ \cdot ⋅ 1 ‾ \overline{1} 1 3 ‾ \overline{3} 3 5 ‾ \overline{5} 5 7 ‾ \overline{7} 7 1 ‾ \overline{1} 1 1 ‾ \overline{1} 1 3 ‾ \overline{3} 3 5 ‾ \overline{5} 5 7 ‾ \overline{7} 7 3 ‾ \overline{3} 3 3 ‾ \overline{3} 3 1 ‾ \overline{1} 1 7 ‾ \overline{7} 7 5 ‾ \overline{5} 5 5 ‾ \overline{5} 5 5 ‾ \overline{5} 5 7 ‾ \overline{7} 7 1 ‾ \overline{1} 1 3 ‾ \overline{3} 3 7 ‾ \overline{7} 7 7 ‾ \overline{7} 7 5 ‾ \overline{5} 5 3 ‾ \overline{3} 3 1 ‾ \overline{1} 1 Die Tafel enthält nur Klassen aus Z 8 ∗ \mathbb{Z}_8^* Z 8 ∗ ​ (abgeschlossen). Auf der Diagonale steht überall 1 ‾ \overline{1} 1 : Hier ist jede Klasse ihr eigenes Inverses .

Zusammenfassung

Z m ∗ \mathbb{Z}_m^* Z m ∗ ​ (auch R m ∗ R_m^* R m ∗ ​ ) ist die Menge der primen Restklassen modulo m m m . Sie hat genau φ ( m ) \varphi(m) φ ( m ) Elemente. ( Z m ∗ , ⋅ ) (\mathbb{Z}_m^*, \cdot) ( Z m ∗ ​ , ⋅ ) ist eine kommutative Gruppe mit neutralem Element 1 ‾ \overline{1} 1 . Jedes Element hat ein Inverses (erweiterter euklidischer Algorithmus). Für eine Primzahl p p p : Z p ∗ = { 1 ‾ , … , p − 1 ‾ } \mathbb{Z}_p^* = \{\overline{1}, \dots, \overline{p - 1}\} Z p ∗ ​ = { 1 , … , p − 1 ​ } .

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: