Teilen kann eigentlich jeder...und schon früh lernt man, dass dabei Reste entstehen können:
Wenn wir durch die Zahl 4 teilen, dann können die Reste 0,1,2, und 3 entstehen.
0:4 = 0 R0 (R bedeutet Rest)
1:4 = 0 R1
2:4 = 0 R2
3:4= 0 R3
4:4 = 1 R0
5:4 = 1 R 1
....13:4 = 3 R 1
Wir fassen alle Zahlen zu einer Restklasse r (modulo 4) zusammen, die beim Teilen durch 4 den Rest r haben:
Restklasse 0 = {0,4,8,12,....}
Restklasse 1 = {1,5,9,13,....}
Restklasse 2 = {2,6,10,14,...}
Restklasse 3 = {3,7,11,15,....}
Die Menge aller Restklassen bei Division durch n bezeichne ich mit Z/nZ, da wir ja alle ganzen Zahlen immer durch n mit Rest r teilen können.
Z/4Z = {0,1,2,3}
Aufgabe:
- Bilde Z/1Z, Z/2Z, Z/3Z
- Was ist die Restklasse 7 bezügl. der Division durch 9? (Kurzform 7 mod 9)
Alle Restklassen bilden bezüglich der Addition für jeden Teiler n eine Gruppe.
Zur Begründung müssen wir nur die Abgeschlossenheit zeigen:
a = k*n + r und b = l*n +r´ gehören bei Division durch n zu den Testklassen r und r´
Dann gilt für a + b:
a + b = k*n+r + l*n+r´= (k+l)*n + r + r´ gehört zur Restklasse (r+r´)
Ist r+r´kleiner als n, so gibt es eine Eintragumng in der Verknüpfugnstafel. Ist r+r´größer als n, so teilt man noch mal durch n und nimmt diesen Rest für die neue Restklasse.
Am besten rechnen wir mal ein Beispiel von Z/4Z durch:
1 + 2 = 3, denn z.B wenn 9 und 10 bei der Division durch 4 einen Rest unter 4 haben, dann auch 19
2 +3 = 1 (denn die Reste 1 und 5 gehören bei Division durch 4 zur gleichen Klasse)
Die Restklasse 0 ist das neutrale Element, und Reste, die sich zum Rest 0 ergänzen, bilden inverse Restklassen.
Man kann ja mal die Verknüpfungstafel von (Z/4Z,+) hinschreiben.
Die Lösung lässt sich leicht überprüfen, denn diese Gruppe ist zyklisch.
Wir haben sie schon kennengelernt.
Für vier Elemente gibt es dann nur noch eine zweite andere (nichtisomorphe) Gruppenstruktur, die nichtzyklische Kleinsche Vierergruppe.
In P16 haben wir alle kleinen Gruppen vorgestellt. Jetzt können wir es sogar noch erweitern:
Alle zyklischen Gruppen mit n Elementen sind strukturgleich (isomorph) zur Gruppe (Z/nZ,+)
Wie ist das mit der Multiplikation?
Da müssen wir immer die Klasse 0 herauslassen. Dann ist 1 das neutrale Elemente.
Die Menge (Z/nZ)\{0}, das sieht kompliziert aus, meint aber nur: "Alle Restklassen ohne Rest 0", bildet nur dann eine Gruppe bezüglich der Multiplikation, wenn n eine Primzahl ist.
Beispiele dazu auszuprobieren und mal für kleine Gruppen die Verknüpfungstafeln hinzuschreiben und zu charakterisieren, dass würde ich euch überlassen.
Interessanterweise bildet auch die Menge aller Restklassen ohne die Klasse 0, deren Reste teilerfremd zu n sind eine eigene Gruppenstruktur bezüglich der Multiplikation.
Sie heißen prime Restklassen Gruppen zur Zahl n
Nehmen wir Z/6Z. Nur die Klassen 1 und 5 enthalten zu 6 teilerfremde Reste.
({1,5},*) bildet eine Gruppe bei der Division durch 6. Das ist die prime Restklassengruppe zur Zahl 6. Sie hat 2 Elemente.
Hinweis: 5*5 = 25 hat den Rest 1 bei Division durch 6.
Die Anzahl der Elemente der primen Restklassengruppe zur Zahl n wird durch die sog. Eulersche Phi-Funktion beschrieben.
In Wikipedia ist eine schöne Darstellung dieser Funktion für die ersten 2000 Werte.
Für die ersten 10 Werte gebe ich sie an:
n: 1 2 3 4 5 6 7 8 9 10
Eulersche Phi-Funktion: 1 1 2 2 4 2 8 4 6 4
Auch hier kann man für weitere kleine n das mal selbst nachvollziehen.
Letztlich gibt die Eulersche Phi-Funktion nichts anderes an, als die Anzahl der zu n teilerfremden Zahlen kleiner als n.
Sie spielt eine wichtige Rolle bei der Erzeugung von Schlüsseln in der Kryptographie.