Restklassen

• Sind a und b ganze Zahlen, so heißt a kongruent b modulo m, wenn ihre Differenz $a-b$ ein ganzzahliges Vielfaches $q\cdot m$ von m ist.
  In Zeichen: $a\equiv b\mathrm{mod}m$ oder kurz $a\equiv b\left(m\right)$.

Beispiele:
$8\equiv 3\left(5\right)$ bedeutet $8-3=1\cdot 5$, und $-7\equiv 8\left(5\right)$ heißt $-7-8=-15=\left(-3\right)\cdot 5$.
Aber es gilt nicht $11\equiv 2\left(5\right)$, da $11-2=9\ne g\cdot 5$ ist.

Dabei ist es von Bedeutung, dass für jede ganze Zahl $m>0$ durch die Relation $a\equiv b\mathrm{mod}m$ eine Äquivalenzrelation in $\mathbb{Z}$ gegeben ist, die $\mathbb{Z}$ in Äquivalenzklassen aufteilt.

• Satz: Es seien a, b und m ganze Zahlen mit $m>0$.
  Die Relation $a\equiv b\left(m\right)$ ist eine Äquivalenzrelation in $\mathbb{Z}$, die sogenannte Kongruenz modulo m.

Beweis:
(1) Die Kongruenz modulo m ist reflexiv, da für alle a aus $\mathbb{Z}$ gilt:
$a\equiv a\left(m\right)\left(wegena-a=0\cdot m\right)$

(2) Die Kongruenz modulo m ist symmetrisch, da für alle a, b aus $\mathbb{Z}$ gilt:
Wenn $a\equiv b\left(m\right)$, dann ist auch $b\equiv a\left(m\right)$, denn $a\equiv b\left(m\right)$ ist äquivalent zu $a-b=g\cdot m$. Damit gilt $-\left(a-b\right)=\left(-g\right)\cdot m$, d.h.
$b-a=\left(-g\right)\cdot m\text{.}$

(3) Die Relation ist auch transitiv, d.h. für alle a, b, c aus $\mathbb{Z}$ folgt aus $a\equiv b\left(m\right)$ und $b\equiv c\left(m\right)$ auch $a\equiv c\left(m\right)$, denn $a\equiv b\left(m\right)$ und $b\equiv c\left(m\right)$ ist äquivalent zu den Gleichungen $a-b=g_1\cdot m$ und $b-c=g_2\cdot m$. Das Ergebnis folgt aus der Addition der beiden Gleichungen:$a-c=\left(a-b\right)+\left(b-c\right)=g_1\cdot m+g_2\cdot m=\left(g_1+g_2\right)\cdot m=g\cdot m$

• Definition: Die Klassen der Klasseneinteilung in $\mathbb{Z}$, welche der Kongruenz modulo m entspricht, heißen Restklassen modulo m.
  Die Schreibweise ${\left[a\right]}_m$ bezeichnet diejenige Restklasse, die die Zahl a enthält.

Für $m=5$ erhält man die folgenden Restklassen:
$\begin{array}{c}{\left[0\right]}_5=\left\{\mathrm{...,}-\mathrm{10,}-\mathrm{5,}\mathrm{0,}\mathrm{5,}\mathrm{10,}\mathrm{...}\right\}\\ {\left[1\right]}_5=\left\{\mathrm{...,}-\mathrm{9,}-\mathrm{4,}\mathrm{1,}\mathrm{6,}\mathrm{11,}\mathrm{...}\right\}\\ {\left[2\right]}_5=\left\{\mathrm{...,}-\mathrm{8,}-\mathrm{3,}\mathrm{2,}\mathrm{7,}\mathrm{12,}\mathrm{...}\right\}\\ {\left[3\right]}_5=\left\{\mathrm{...,}-\mathrm{7,}-\mathrm{2,}\mathrm{3,}\mathrm{8,}\mathrm{13,}\mathrm{...}\right\}\\ {\left[4\right]}_5=\left\{\mathrm{...,}-\mathrm{6,}-\mathrm{1,}\mathrm{4,}\mathrm{9,}\mathrm{14,}\mathrm{...}\right\}\end{array}$

Der Name Restklasse erklärt sich aus folgendem Zusammenhang:

• Satz: Es gilt $a\equiv b\left(m\right)$ genau dann, wenn a und b bei der Division durch m den gleichen Rest r mit $0\le r<m$ lassen.

Daraus folgt, dass es genau m Restklassen modulo m gibt, nämlich ${\left[0\right]}_m,{\left[1\right]}_m,\mathrm{...,}{\left[m-1\right]}_m.$ Die Zahlen $\mathrm{0,}\mathrm{1,}\mathrm{...,}m-1$ 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 $a=g_1\cdot m+rundb=g_2\cdot m+r\left(mit0\le r<m\right)$
gilt, folgt:
$a-b=\left(g_2-g_1\right)\cdot m=g\cdot m$
Da $g_2-g_1\in \mathbb{Z}$ ist, ergibt sich $a\equiv b\left(m\right)$.
Umgekehrt ergibt sich aus $a-b=g\cdot m$ mit $g\in \mathbb{Z}$ durch Einsetzen in $a=g_1\cdot m+r$ mit $0\le r<m$, dass auch b bei der Division durch m den gleichen Rest r lässt, da
$\begin{array}{c}b=a-g\cdot m=g_1\cdot m+r-g\cdot m\\ =\left(g_1-g\right)\cdot m+r\left(mit{g}_1-g\in \mathbb{Z}\right)\end{array}$
ist.

Es sei noch darauf hingewiesen, dass in der Restklasse ${\left[0\right]}_m$ 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:$a\equiv 0\left(m\right)genaudann,wennm|a$

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 $a\text{'}\equiv a\left(m\right)undb\text{'}\equiv b\left(m\right).$ Dann gilt $a\text{'}+b\text{'}\equiv a+b\left(m\right)unda\text{'}b\text{'}\equiv ab\left(m\right).$ 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:
$\begin{array}{l}{\left[a\right]}_m+{\left[b\right]}_m={\left[a+b\right]}_m\\ {\left[a\right]}_m\cdot \left[b\right]\begin{array}{cc}{}_m={\left[a\cdot b\right]}_m& (\ast )\end{array}\end{array}$
So gilt zum Beispiel ${\left[2\right]}_5+{\left[4\right]}_5={\left[6\right]}_5={\left[1\right]}_5$, aber auch ${\left[2\right]}_5+{\left[4\right]}_5={\left[7\right]}_5+{\left[14\right]}_5={\left[7+14\right]}_5={\left[21\right]}_5={\left[1\right]}_5$.

Die Operationseigenschaften der Addition und der Multiplikation in $\mathbb{Z}$ ü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 $(\ast )$ definierten Addition und Multiplikation einen kommutativen Ring mit ${\left[1\right]}_m$, den sogenannten Restklassenring von $\mathbb{Z}$ modulo m, bilden (in Zeichen: $\mathbb{Z}/m\mathbb{Z}$ ).

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 $\mathbb{Z}/6\mathbb{Z}$ angegeben wird. In diesem Beispiel bedeutet $\left[a\right]$ stets ${\left[a\right]}_6$.

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.