Prime Restklassen

Bei normalen Zahlen kann man jede Zahl außer 0 „rückgängig malnehmen“: 3 cdot frac{1}{3} = 1 . Bei Restklassen modulo m|Restklassen gibt es keine Brüche. Trotzdem findet man oft ein Gegenstück: In mathbb{Z} {10} ist overline{3} cdot overline{7} = overline{21} = overline{1} . Aber nicht immer: Für overline{4} in mathbb{Z} {10} gibt es keins. Die Klassen, bei denen es klappt, heißen prime Restklassen . Sie sind die Grundlage für die Euler'sche Phi-Funktion , den Satz von Euler-Fermat und die RSA-Verschlüsselung. Definition Die Restklasse a + m mathbb{Z} = overline{a} heißt prime Restklasse , wenn a und m Teilerfremdheit|teilerfremd sind: overline{a} text{ prim modulo } m quad Longleftrightarrow quad text{ggT}(a, m) = 1 Es ist egal, welchen Repräsentanten man nimmt – alle Zahlen einer Klasse haben denselben ggT mit m . Warum ist das wichtig? overline{a} text{ ist prim} quad Longleftrightarrow quad overline{a} text{ hat ein Inverses bezüglich } cdot Das Inverse berechnet man mit dem Erweiterter euklidischer Algorithmus|erweiterten euklidischen Algorithmus . Achtung: „Prim“ heißt hier nicht , dass a eine Primzahl sein muss. overline{9} ist modulo 10 prim, overline{5} ist es nicht. Sonderfall: Ist m eine Primzahl, sind alle Klassen außer overline{0} prim. Ist 3 + 7 mathbb{Z} eine prime Restklasse? Und 6 + 9 mathbb{Z} ? text{ggT}(3, 7) = 1 qquad Rightarrow qquad 3 + 7 mathbb{Z} text{ ist prim} text{ggT}(6, 9) = 3 qquad Rightarrow qquad 6 + 9 mathbb{Z} text{ ist nicht prim} Welche Kl

Worum geht's?

Bei normalen Zahlen kann man jede Zahl außer 0 0 0 „rückgängig malnehmen“: 3 ⋅ 1 3 = 1 3 \cdot \frac{1}{3} = 1 3 ⋅ 3 1 ​ = 1 . Bei Restklassen gibt es keine Brüche. Trotzdem findet man oft ein Gegenstück: In Z 10 \mathbb{Z}_{10} Z 10 ​ ist 3 ‾ ⋅ 7 ‾ = 21 ‾ = 1 ‾ \overline{3} \cdot \overline{7} = \overline{21} = \overline{1} 3 ⋅ 7 = 21 = 1 . Aber nicht immer: Für 4 ‾ \overline{4} 4 in Z 10 \mathbb{Z}_{10} Z 10 ​ gibt es keins. Die Klassen, bei denen es klappt, heißen prime Restklassen . Sie sind die Grundlage für die Euler'sche Phi-Funktion , den Satz von Euler-Fermat und die RSA-Verschlüsselung.

Formel mit Erklärung

Definition Die Restklasse a + m Z = a ‾ a + m\mathbb{Z} = \overline{a} a + m Z = a heißt prime Restklasse , wenn a a a und m m m teilerfremd sind: a ‾  prim modulo  m ⟺ ggT ( a , m ) = 1 \overline{a} \text{ prim modulo } m \quad\Longleftrightarrow\quad \text{ggT}(a, m) = 1 a  prim modulo  m ⟺ ggT ( a , m ) = 1 Es ist egal, welchen Repräsentanten man nimmt – alle Zahlen einer Klasse haben denselben ggT mit m m m . Warum ist das wichtig? \overline{a} \text{ ist prim} \quad\Longleftrightarrow\quad \overline{a} \text{ \hat ein Inverses bezüglich } \cdot Das Inverse berechnet man mit dem erweiterten euklidischen Algorithmus . Achtung: „Prim“ heißt hier nicht , dass a a a eine Primzahl sein muss. 9 ‾ \overline{9} 9 ist modulo 10 10 10 prim, 5 ‾ \overline{5} 5 ist es nicht. Sonderfall: Ist m m m eine Primzahl, sind alle Klassen außer 0 ‾ \overline{0} 0 prim.

Beispiele

Leicht#1
Ist 3 + 7 Z 3 + 7\mathbb{Z} 3 + 7 Z eine prime Restklasse? Und 6 + 9 Z 6 + 9\mathbb{Z} 6 + 9 Z ? ggT ( 3 , 7 ) = 1 ⇒ 3 + 7 Z  ist prim \text{ggT}(3, 7) = 1 \qquad\Rightarrow\qquad 3 + 7\mathbb{Z} \text{ ist prim} ggT ( 3 , 7 ) = 1 ⇒ 3 + 7 Z  ist prim ggT ( 6 , 9 ) = 3 ⇒ 6 + 9 Z  ist nicht prim \text{ggT}(6, 9) = 3 \qquad\Rightarrow\qquad 6 + 9\mathbb{Z} \text{ ist nicht prim} ggT ( 6 , 9 ) = 3 ⇒ 6 + 9 Z  ist nicht prim

Zusammenfassung

a ‾ \overline{a} a ist eine prime Restklasse modulo m m m , wenn ggT ( a , m ) = 1 \text{ggT}(a, m) = 1 ggT ( a , m ) = 1 . Genau die primen Restklassen haben ein Inverses bezüglich der Multiplikation. „Prim“ bezieht sich auf die Teilerfremdheit zu m m m , nicht darauf, dass a a a eine Primzahl ist. Ist m m m eine Primzahl, sind alle Klassen außer 0 ‾ \overline{0} 0 prim. Die Anzahl der primen Restklassen ist φ ( m ) \varphi(m) φ ( m ) .

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: