Die Kongruenzrelation

Wir betrachten nun Zahlen, die bei der Division durch einen Divisor d ≥ 1 den gleichen Rest haben und in diesem Sinne „ähnlich“ oder „verwandt“ sind. Eine wichtige Beobachtung hierzu ist:

Satz (Charakterisierung von „gleicher Rest“)

Sei d ≥ 1. Dann haben zwei Zahlen a und b bei Division durch d genau dann den gleichen Rest, wenn ihre Differenz a − b durch d teilbar ist.

Beweis

Seien a = q₁d + r₁, b = q₂d + r₂ die Divisionen mit Rest von a und b durch d. Dann gilt

a − b = (q₁ − q₂) d + r₁ − r₂ mit −d < r₁ − r₂ < d.

Aus dieser Darstellung lässt sich die Äquivalenz ablesen.

Die Eigenschaften „gleicher Rest bei Division durch d“ und „die Differenz ist durch d teilbar“ sind nach dem Satz äquivalent, die zweite Eigenschaft erweist sich aber als leichter zu handhaben. Wir bevorzugen sie deswegen in der folgenden Definition, die eine der wichtigsten Begriffsbildungen der Zahlentheorie beinhaltet.

Definition (Kongruenz, modulo)

Sei d ≥ 1. Zwei Zahlen a und b heißen kongruent modulo d, falls d | (a − b). In Zeichen schreiben wir

a ≡ b mod(d) [ gelesen: a kongruent b modulo d ].

Statt d für „Divisor“ schreiben wir im Folgenden zumeist m für „Modul“. Der Begriff geht auf das lateinische Wort „modulus“ für „Maß“ zurück. „Modulo“ bedeutet „mit dem Maß“. Die Relation a ≡ b mod(m) besagt also, dass a und b kongruent/gleichwertig/äquivalent sind, wenn sie mit dem Maß m gemessen werden. Die Verwendung des geometrischen Begriffs der Kongruenz (Übereinstimmung in Sinne der Deckungsgleichheit) lässt sich so erklären: Zwei Zahlen a und b sind genau dann kongruent, wenn sie durch Verschiebungen in der Schrittweite m zur Deckung gebracht werden. Denn der Abstand der Zahlen ist im Fall der Kongruenz (und nur dann) ein Vielfaches von m.

Wir führen noch alternative Notationen ein:

Notation

Wir schreiben statt a ≡ b mod(m) auch

a ≡ b (m) oder a ≡ _m b.

Beispiele

(1)	4 ≡ 9 (5), 4 ≡ 4 (5), 4 ≡ −1 (5).

(2)	0 ≡ −20 (5), 1 ≡ −19 (5), 2 ≡ −18 (5), −1 ≡ −21 (5).

(3)	Da jede ganze Zahl ein Vielfaches der 1 ist, sind je zwei Zahlen kongruent modulo 1, d. h.: Für alle a, b gilt a ≡ b (1). Die Kongruenz modulo 1 sieht also alle ganzen Zahlen als gleichwertig/äquivalent an.

(4)	Für alle a, b gilt: a ≡ b (2) genau dann, wenn a und b haben die gleiche Parität. Dabei haben a und b die gleiche Parität, wenn a und b beide gerade oder beide ungerade sind.

Leicht zu zeigende Eigenschaften der Kongruenz sind:

Satz (Eigenschaften der Kongruenz, I)

Sei m ≥ 1. Dann gilt für alle ganzen Zahlen a, b, c:

(a)	a ≡ a (m),(Reflexivität)

(b)	a ≡ b (m) impliziert b ≡ a (m),(Symmetrie)

(c)	a ≡ b (m) und b ≡ c (m) impliziert a ≡ c (m).(Transitivität)

Eine Relation ∼ auf einer Menge M, die drei Eigenschaften des Satzes erfüllt (mit a ∼ b statt a ≡ b (m)), heißt eine Äquivalenzrelation auf M. Der Satz besagt also, dass für jede Zahl m ≥ 1 die Relation ≡ _m eine Äquivalenzrelation auf den ganzen Zahlen ist.

Mit Blick auf die Transitivität führen wir noch eine nützliche Vereinfachung der Notation ein.

Notation

a ≡ b ≡ c ≡ … (m) bedeutet a ≡ b (m) und b ≡ c (m) und …

Damit können Kongruenzen wie Identitäten und Abschätzungen in Ketten behandelt werden:

Beispiel

4 ≡ −1 ≡ −11 ≡ −6 ≡ 4 (5).

Für Kongruenzen existiert ein eleganter Rechenkalkül. Die wichtigsten Regeln dieses Kalküls sind (Beweis als Übung):

Satz (Eigenschaften der Kongruenz, II)

Sei m ≥ 1, und seien a, b, c, d ganze Zahlen mit

a ≡ b (m) und c ≡ d (m).

Dann gilt:

(K1)	a + c ≡ b + d (m),
(K2)	n a ≡ n b (m)	für alle n,
(K3)	a c ≡ b d (m),
(K4)	aⁿ ≡ bⁿ (m)	für alle n ≥ 0,
(K5)	a ≡ b (d)	für alle Teiler d von m mit d ≥ 1.

Die Eigenschaften (K1) und (K3) können wir auch so ausdrücken:

Die Kongruenzrelation ≡ _m respektiert die Addition und die Multiplikation auf den ganzen Zahlen ℤ.

Wir können deswegen in Termen, die aus den ganzen Zahlen mit Hilfe der Operationen + und · aufgebaut sind, „kongruent ersetzen“. Damit werden viele Berechnungen überraschend einfach:

Beispiel

Sei m = 10. Dann gilt

3¹²² ≡ (3 · 3)⁶¹ ≡ 9⁶¹ ≡ (−1)⁶¹ ≡ −1 ≡ 9 (10).

Damit ist die 9 die letzte Ziffer der Potenz 3¹²² in Dezimaldarstellung.

Alternativ können wir auch so argumentieren: Die letzten Ziffern in den Potenzen 3¹, 3², 3³, … im Dezimalsystem bilden die periodische Folge

3, 9, 7, 1, 3, 9, 7, 1, 3, 9, 7, 1, …

Weiter gilt 122 ≡ 2 (4), sodass an der Position 122 der periodischen Folge die 9 steht.

In Oktaldarstellung (m = 8) gilt dagegen

3¹²² ≡ (9)⁶¹ ≡ 1⁶¹ ≡ 1 (8),

sodass die letzte Ziffer bei dieser Darstellung die 1 ist.

Die Kongruenzrelationen lassen sich auf verschiedene Weisen visualisieren. Wie für die Teilbarkeit können wir die Relationen als Punktmengen der Ebene zeichnen. Dadurch ergeben sich Streifenmuster. Eine andere Möglichkeit ist, sich die Kongruenzrelationen als Aufwicklungen der ganzen Zahlen vorzustellen. Die folgenden Diagramme geben einige Beispiele.

Eine Visualisierung der Kongruenz modulo 5: Gezeigt sind alle Paare (a, b)  ∈  ℤ², |a|, |b| ≤ 10, mit a  ≡ b mod(5).

Größerer Bereich mit dem Modul m = 10

Aufwicklung von ℤ durch die Kongruenz modulo 5

Aufwicklung von ℤ durch die Kongruenz modulo 12

Die zweite Visualisierung zeigt besonders schön, wie die ganzen Zahlen ℤ durch eine Kongruenzrelation ≡ _m in m unendliche Klassen untereinander kongruenter Zahlen eingeteilt werden. Bei zeilenweiser Anordnung ergibt sich:

Zeilen-Zerlegung von ℤ durch die Kongruenz modulo 3

Zeilen-Zerlegung von ℤ durch die Kongruenz modulo 7

Nicht zuletzt können wir auch gleichmäßige Sprünge auf der Zahlengeraden betrachten:

Visualisierung der Kongruenz modulo 5 an der Zahlengeraden