Restklassen

Jede positive ganze Zahl m gestattet es, in der Menge der ganzen Zahlen eine Relation der folgenden Art zu definieren:

• Sind a und b ganze Zahlen, so heißt a kongruent b modulo m, wenn ihre Differenz ein ganzzahliges Vielfaches von m ist.
  In Zeichen: oder kurz .

Beispiele:
bedeutet , und heißt .
Aber es gilt nicht , da ist.

Dabei ist es von Bedeutung, dass für jede ganze Zahl durch die Relation eine Äquivalenzrelation in gegeben ist, die in Äquivalenzklassen aufteilt.

• Satz: Es seien a, b und m ganze Zahlen mit .
  Die Relation ist eine Äquivalenzrelation in , die sogenannte Kongruenz modulo m.

Beweis:
(1) Die Kongruenz modulo m ist reflexiv, da für alle a aus gilt:


(2) Die Kongruenz modulo m ist symmetrisch, da für alle a, b aus gilt:
Wenn , dann ist auch , denn ist äquivalent zu . Damit gilt , d.h.


(3) Die Relation ist auch transitiv, d.h., für alle a, b, c aus folgt aus und auch , denn und ist äquivalent zu den Gleichungen und . Das Ergebnis folgt aus der Addition der beiden Gleichungen:

• Definition: Die Klassen der Klasseneinteilung in , welche der Kongruenz modulo m entspricht, heißen Restklassen modulo m.
  Die Schreibweise bezeichnet diejenige Restklasse, die die Zahl a enthält.

Für erhält man die folgenden Restklassen:

Der Name Restklasse erklärt sich aus folgendem Zusammenhang:

• Satz: Es gilt genau dann, wenn a und b bei der Division durch m den gleichen Rest r mit lassen.

Daraus folgt, dass es genau m Restklassen modulo m gibt, nämlich Die Zahlen bilden ein vollständiges Repräsentantensystem der Klassen modulo m, welches das kleinste nichtnegative Repräsentantensystem genannt wird.
Beweis (des obigen Satzes):
Falls beide Zahlen bei der Division durch m den gleichen Rest lassen, also
gilt, folgt:

Da ist, ergibt sich .
Umgekehrt ergibt sich aus mit durch Einsetzen in mit , dass auch b bei der Division durch m den gleichen Rest r lässt, da

ist.

Es sei noch darauf hingewiesen, dass in der Restklasse genau diejenigen ganzen Zahlen liegen, die Vielfache von m sind. Deshalb kann man auch die Teilbarkeitsrelation mit Hilfe der Kongruenz modulo m folgendermaßen formulieren:

Rechnen mit Kongruenzen
Mit Kongruenzen kann man wie mit Gleichungen rechnen, und das von CARL FRIEDRICH GAUSS (1777 bis 1855) stammende Kongruenzzeichen erinnert auch an das Gleichheitszeichen.
Es sei Dann gilt Damit ist es möglich, in der Menge der Restklassen eine Addition und eine Multiplikation zu erklären, die sich auf die entsprechenden Operationseigenschaften für die Repräsentanten stützt, aber nicht von der Wahl der Repräsentanten abhängt.
Die Addition und die Multiplikation von Restklassen lassen sich wie folgt definieren:

So gilt zum Beispiel , aber auch .

Die Operationseigenschaften der Addition und der Multiplikation in übertragen sich auf die Menge der Restklassen modulo m.

Es sei hier nur noch vermerkt, dass die Menge der m Restklassen modulo m bezüglich der unter definierten Addition und Multiplikation einen kommutativen Ring mit , den sogenannten Restklassenring von modulo m, bilden (in Zeichen: ).
Damit sind wir zu Beispielen für Ringe gelangt, die nur aus endlich vielen Elementen bestehen. Sie haben u.a. den Vorteil, dass man die Addition und die Multiplikation in Form von Strukturtafeln aufschreiben kann, was im Folgenden für den Restklassenring angegeben wird. In diesem Beispiel bedeutet stets .
Die Additions- und die Multiplikationstafel für die Restklassen modulo 6 haben folgende Form:



Eine Anwendung im Schulstoff findet die Kongruenzrelation u.a. in der Ableitung der Teilbarkeitsregeln.