Restklassen

Teilbarkeitsbeziehungen spielen bei vielen zahlentheoretischen Überlegungen eine Rolle.
So kann man z. B. die Reste untersuchen, die natürliche Zahlen bei der Division durch eine Zahl b lassen.

Bei Division durch 5 können die Reste 0, 1, 2, 3 und 4 auftreten;
den Rest 0 lassen die Zahlen 0, 5, 10, 15, ..., 5n $\left(n\in \mathbb{N}\right)$,
den Rest 1 lassen die Zahlen 1, 6, 11, 16, ..., 5n + 1 $\left(n\in \mathbb{N}\right)$,
den Rest 2 lassen die Zahlen 2, 7, 12, 17, ..., 5n + 2 $\left(n\in \mathbb{N}\right)$,
den Rest 3 lassen die Zahlen 3, 8, 13, 18, ..., 5n + 3 $\left(n\in \mathbb{N}\right)$,
den Rest 4 lassen die Zahlen 4, 9, 14, 19, ..., 5n + 4 $\left(n\in \mathbb{N}\right)$.

Damit ist die Menge der natürlichen Zahlen $\mathbb{N}$ in 5 Teilmengen
$K_i$ (i = 0, 1, 2, 3, 4) natürlicher Zahlen, die bei Division durch 5 den Rest i lassen, unterteilt. Keine dieser Teilmengen ist leer, auch gibt es keine Zahl, die in zwei Teilmengen vorkommt. Die Gesamtheit (Vereinigung) der Teilmengen ergibt $\mathbb{N}$.

Damit liegt eine Klasseneinteilung vor und die Relation „die Zahl b lässt bei Division durch 5 denselben Rest wie die Zahl a“ (aRb) ist eine Äquivalenzrelation.

Eine Relation aRb heißt Äquivalenzrelation, wenn sie folgende Bedingungen erfüllt:
Sie ist

• reflexiv, d. h. es gilt aRa,
• symmetrisch, d. h. aus aRb folgt bRa,
• transitiv, d. h. aus aRb und bRc folgt aRc
  (wenn a den gleichen Rest lässt wie b und b den gleichen wie c, dann lassen auch a und c den gleichen Rest).

Gibt es in einer Menge eine Äquivalenzrelation, so gehört zu ihr eindeutig eine Klasseneinteilung (Unterteilung in Äquivalenzklassen) dieser Menge. Umgekehrt gehört zu jeder Klasseneinteilung eine Äquivalenzrelation.

Die Teilmengen $K_0$, $K_1$, $K_2$, $K_3$ und $K_4$ heißen Restklassen modulo 5.
Wählt man aus jeder Klasse einen Vertreter aus, so erhält man ein vollständiges Restesystem modulo 5. Die Menge $R=\left\{15;6;22;3;29\right\}$ ist ein solches. Wählt man aus jeder Restklasse die kleinste Zahl aus, erhält man das System der kleinsten Reste.
$R_k=\left\{0;1;2;3;4\right\}$ ist das System der kleinsten Reste modulo 5.
Restklassen lassen sich für jede natürliche Zahl b > 1 bilden.

Wenn man die Teilbarkeitsrelation auf ganze Zahlen erweitert, was durchaus üblich ist, können für die Menge der ganzen Zahlen $\mathbb{Z}$ ebenfalls Restklassen gebildet werden. Die Zahlen –2 und 3 liegen dann modulo 5 in derselben Restklasse.