Nimmt man nun eine (unendlich große) Menge von ganzen Zahlen und beobachtet, was passiert wenn man alle diese Zahlen modulo einer konstanten, ganzen Zahlen rechnet, so kann man interessantes beobachten: Es entsteht nur eine endliche Anzahl von verschiedenen Resten! Ist die Zahl modulo der man rechnet n so können maximal n verschiedene Reste entstehen.

Diese Reste können logischerweise auch nur im Bereich zwischen 0 und n-1 sein. 0 dann, wenn die Zahl ein Vielfaches von n ist. Alle anderen Reste ergeben sich, für die Zahlen zwischen zwei aufeinanderfolgenden Vielfachen von n. Für n=3 sieht das zum Beispiel wie folgt aus:

Das bedeutet, dass viele Zahlen aus unserer Menge den gleichen Rest modulo 3 erzeugen. Zahlen die den gleichen Rest erzeugen nennt man zueinander kongruent. Im obigen Beispiel sind 0,3,6, ... kongruent bezüglich modulo 3, genauso wie 1,4,7, ... oder 2,5,8, ... Das kann man auch schön formal definieren:

Seien a,b ganze Zahlen und n eine natürliche Zahl. Die Zahlen a und b heißen kongruent modulo n, wenn a-b durch n teilbar ist. Mathematisch schreibt man a ≡ b mod n.

Überlege Dir was es bedeutet, wenn die Differenz a-b durch n teilbar ist! Schreibe Dir einige Paare von Zahlen in dein Lerntagebuch, für die das gilt!

Ein alternative, aber gleichbedeutende Definition von Kongruenz modulo einer Zahl ist:

Zwei ganze Zahlen a und b sind genau dann kongruent modulo n, wenn a und b bei Division durch n den selben Rest lassen.

Die verschiedenen Reste die sich bei Division einer Menge von ganzen Zahlen durch eine fixe Zahl n ergeben nennt man Restklassen. Man sagt auch, dass die Zahlenmenge durch die Modulo-Operation in Restklassen "zerfällt". Für eine Divisor n gibt es genau n verschiedene Reste, nämlich die Werte 0, 1, 2, ... n-1. In der Praxis wird nicht zwischen den Resten und den entstehenden Restklassen unterschieden.

Die Restklassen werden immer nach der Zahl benannt, die der Divisor bei der Erzeugung war. Also z.B. Z/3Z (sprich: "Z modulo 3 Z"), oder Z/7Z bzw. allgemein Z/nZ.

Das Rechnen mit Restklassen birgt einige coole Eigenschaften, wie wir gleich sehen werden. Sind a und b Elemente bestimmter Restklassen, so können wir auch die Restklasse von a+b ausrechnen. Oder die Restklasse von a*b. Es mag erstaunlich klingen, aber die Restklasse dieser Ergebnisse hängt überhaupt nicht von den konkreten Elementen a und b ab, sondern lediglich davon aus welchen Restklassen diese beiden Elemente stammen!

Nehmen wir aus dem vorigen Beispiel die Zahlen 1 und 7: die Zahlen haben modulo 3 beide die Restklasse 1, wie du leicht nachrechnen kannst. Welche Restklasse hat die Summe der beiden Zahlen?

Genau, es ist 2. Welches Ergebnis kommt heraus, wenn du die beiden urspünglichen Restklassen addierst?

Genau, auch 2!

Oder nimm andere Zahlen, wie z.B. 4 und 22. Berechne wieder die Restklassen der beiden Zahlen modulo 3 und auch die Restklasse der Summe der beiden Zahlen. Was fällt Die auf? Notiere deine Beobachtung in deinem Lerntagebuch!

Verwende diese GeoGebra Datei zum Experimentieren mit Resten der ganzzahligen Division für deine Experimente!

Diese Zusammenhänge sind kein Zufall, sondern können mathematisch leicht bewiesen werden:

Haben a₁ und a₂ die gleiche Restklasse modulo n, sowie b₁ und b₂ auch, dann gilt ja laut obiger Definition, dass a₁-a₂ = q₁*n und b₁-b₂ = q₂*n. Setzt man diese Zerlegung nun in die Summe von (a₁+b₁) bzw. (a₂+b₂) ein, so erhält man: (a₁+b₁) - (a₂+b₂) = (q₁+q₂)*n und damit ist (a₁+b₁) mod n = (a₂+b₂) mod n.

Versuche auch noch andere Paare von Zahlen zu finden und prüfe damit in deinem Lerntagebuch, ob diese Beobachtung auch für die Multiplikation gilt!

Wir halten ein wichtiges Ergebnis fest, das, wie wir noch sehen werden, ein sehr großer Vorteil ist:

Statt mit tatsächlichen teilweisen sehr großen Zahlen zu rechnen, kann man sich bei Restklassen als damit begnügen mit den jeweiligen Restklassen zu rechnen!

Es gilt also:

• (a+b) mod n = (a mod n + b mod n) mod n
• Dementsprechend auch: (a-b) mod n = (a mod n)-(b mod n) mod n
   
• (a*b) mod n = (a mod n)*(b mod n) mod n
• Und daraus folgt: (a^b) mod n = (a mod n)^b mod n

Je nachdem welche Zahl n man für die Modulo-Operation verwendet, haben die entstehenden Restklassen unterschiedliche Eigenschaften. Ein besonders günstiger Fall tritt ein, wenn für n eine Primzahl verwendet wird. Die dadurch entstehenden Restklassen erfüllen soviele grundlegende Eigenschaften, dass damit eine algebraische Struktur namens Körper entsteht. Weil dadurch erst die meisten Rechenregeln die wir kennen Gültigkeit erlangen, werden in der Praxis wie z.B. im Bereich der Kryptographie so gerne Primzahlen verwendet.

Solange man eine endliche Menge von Zahlen hat, kann man z.B. auch alle möglichen Additionen und Multiplikationen in einer Tabelle darstellen. Nachdem wir bei Restklassen ja wie gesagt nur n verschiedene Elemente zu betrachten haben, können wir dies hier auch machen. Für kleine n, ergeben sich damit sehr übersichtliche Tabellen. Hier ein Beispiel für n=3:

(Grafik von http://www.grundstudium.info/linearealgebra/lineare_algebra_grundlagennode39.php)

Im obigen Beispiel ist n=3 eine Primzahl. Ist n keine Primzahl, so ergeben sich nämlich einige Probleme. Sieh dir als Beispiel dazu einmal folgende Grafik an und vergleiche sie mit oben stehenden Grafik für n=3. Was fällt dir auf, wenn du die einzelnen Einträge jeder Zeile betrachtest?

(Grafik von http://www.grundstudium.info/linearealgebra/lineare_algebra_grundlagennode39.php)

In der Additionstabelle gibt es noch keine dramatischen Unterschiede. Sehr wohl aber, in der Multiplikationstabelle. Vor allem in der Zeile bzw. Spalte die mit "2" beschriftet ist. Hier finden wir nicht alle möglichen Elemente 0,...,3, sondern lediglich 0 und 2, diese kommen dafür doppelt vor. Welche Konsequenzen hat das?

Das ist leider das untrügerische Anzeichen dafür, dass die Restklassen für n=4 keine Körper bilden. In einem Körper existiert auch für die Multiplikation für jedes Element a (außer 0) ein eindeutiges inverses Element b, so dass a*b = 1 ergibt. Was ist hier das inverse Element von 2? Es gibt leider keines und damit ergibt diese Menge keinen Körper.

Du kannst diese Eigenschaft für andere algebraische Körper nachprüfen, z.B. für die reellen Zahlen, oder auch für die Restklassen von n=3 oder n=7. Notiere die Ergebnisse in dein Lerntagebuch!

Verwende diese Mathematica Notebook mit Beispielen zum Rechnen mit Restklassen um den Umgang mit den Restklassen zu üben. Das erste Beispiel zeigt dir, dass man sich wesentlich leichter tut, wenn man tatsächlich statt mit den großen Zahlen nur mit den Resten rechnet. Das zweite Beispiel führt dir vor Augen, warum es wichtig ist in einem Körper zu rechnen. Denn nur dort existieren die inversen Elemente und damit ein weites Anwendungsspektrum der Restklassen!