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?
Formel mit Erklärung
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
