3. Grundlagen über Kongruenzen
Wir stellen im Überblick einige Grundlagen des Modulo-Rechnens zusammen. Für eine ausführlichere Darstellung kann der Leser beispielsweise die „Einführung in die Mathematik“ (Teil 2.1) des Autors heranziehen.
Die Division mit Rest
Ausgangspunkt ist der folgende Satz:
Satz (Division mit Rest)
Seien a, d ganze Zahlen mit d ≥ 1. Dann gibt es eindeutige q und r mit
a = q d + r, 0 ≤ r < d.
Weiter gilt r = 0 genau dann, wenn d ein Teiler von a ist.
Beweis
zur Existenz:
Sei q die größte ganze Zahl mit qd ≤ a. Weiter sei r = a − qd. Dann gilt
a = qd + a − qd = qd + r mit r ≥ 0.
Wegen (q + 1)d > a ist d > a − qd = r. Also sind q und r wie im Satz.
zur Eindeutigkeit:
Seien q1, q2, r1, r2 ganze Zahlen mit
a = q1d + r1 = q2d + r2 mit 0 ≤ r1 ≤ r2 < d.
Dann gilt
r2 − r1 = (q1 − q2)d.
Folglich ist r2 − r1 ein Vielfaches von d. Wegen 0 ≤ r1 ≤ r2 < d gilt 0 ≤ r2 − r1 ≤ d − 1. Also ist r2 − r1 = 0, da die Null das einzige Vielfache von d im Intervall { 0, …, d − 1 } ist. Folglich ist r1 = r2. Aus
0 = r2 − r1 = (q1 − q2)d
ergibt sich wegen d ≠ 0, dass q1 = q2.
Quotienten, Reste und die Kongruenzrelation modulo
Definition (Quotient, Rest)
Gilt a = q d + r wie im Satz über die Division mit Rest, so heißt q der Quotient und r der Rest der Division von a durch d.
Sehr nützlich 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 = q1d + r1, b = q2d + r2 die Divisionen mit Rest von a und b durch d. Dann gilt
a − b = (q1 − q2) d + r1 − r2 mit −d < r1 − r2 < d.
Aus dieser Darstellung lässt sich die Äquivalenz ablesen.
Damit können wir nun definieren:
Definition (Kongruenz, modulo)
Sei m ≥ 1. Zwei Zahlen a und b heißen kongruent modulo m, falls m ein Teiler von a − b ist. In Zeichen schreiben wir
a ≡ b mod(m) [ gelesen: a kongruent b modulo m ].
Statt d für „Divisor“ wird in der Theorie der Kongruenzen traditionell der Buchstabe m für „Modul“ verwendet. Das Wort „modulo“ geht auf das Lateinsche „modulus“ für „Maß“ zurück. Zwei ganze Zahlen a und b sind kongruent modulo m, wenn sie bei der Division durch m (beim „Messen mit dem Maßstab m“) den gleichen Rest hinterlassen. Wickeln wir die ganzen Zahlen derart auf, dass m Zahlen eine volle Windung ergeben, so bedeutet a ≡ b mod(m), dass die Zahlen a und b bei der Aufwicklung übereinander zu liegen kommen.
Notation
Wir schreiben statt a ≡ b mod(m) auch
a ≡ b (m) oder a ≡ m b.
Beispielsweise gilt 2 ≡ 7 (5) und 7 ≡ −3 (5). Die zur Zahl 7 modulo 5 kongruenten Zahlen sind …, −8, −3, 2, 7, 12, 17, … Sie bilden eine beidseitig unendliche arithmetische Progression in den ganzen Zahlen der Schrittweite 5.
Wir schreiben im Folgenden oft wieder (a, b) statt ggT(a, b). Damit bedeutet (a, b) = 1, dass die ganzen Zahlen a und b teilerfremd sind.
Eigenschaften der Kongruenz
Die Kongruenz modulo m ist, wie leicht zu zeigen ist, eine Äquivalenzrelation:
Satz (Eigenschaften der Kongruenz)
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) |
Wir schreiben kurz a ≡ b ≡ c (m) statt a ≡ b (m) und b ≡ c mod(m) (Kettennotation wie für =, <, ≤, …). Die wichtigsten Recheneigenschaften sind:
Satz (Kongruenzkalkül)
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) | an ≡ bn (m) | für alle n ≥ 0, |
| (K5) | a ≡ b (d) | für alle Teiler d von m mit d ≥ 1. |
Darüber hinaus gilt:
Satz (Kürzungsregel für Kongruenzen)
Seien a, b, c, m ∈ ℤ mit m ≥ 1. Dann sind äquivalent:
(a) | ca ≡ cb mod(m). |
(b) | a ≡ b mod(m/(c, m)). |
Sind c und m teilerfremd, so gilt
ca ≡ cb mod(m) genau dann, wenn a ≡ b mod(m)
So folgt zum Beispiel aus 2a ≡ 2b (5), dass a ≡ b (5). Dagegen können wir in den Kongruenzen
2 · 4 ≡ 2 · 3 mod(2) oder 2 · 13 ≡ 2 · 4 mod(6)
die 2 nicht einfach kürzen. Aus (2, 2) = 2 erhalten wir 4 ≡ 3 (1) und aus (2, 6) = 2 ergibt sich 13 ≡ 4 (3).
Restsysteme
Die Eulersche φ-Funktion spielt in der Theorie der Kongruenzen eine wichtige Rolle. Im Folgenden sei r1, …, rφ(m) eine Aufzählung der zu m teilerfremden Zahlen im Intervall { 1, …, m }. Für m = 12 erhalten wir beispielsweise 1, 5, 7, 11 mit φ(12) = 4. Wir definieren:
Definition (vollständiges und reduziertes Restsystem)
Sei m ≥ 1.
(a) | Eine Menge A ⊆ ℤ heißt ein (vollständiges) Restsystem modulo m, falls für alle r = 0, …, m − 1 genau ein a ∈ A existiert mit a ≡ r (m). |
(b) | Eine Menge B ⊆ ℤ heißt ein reduziertes Restsystem modulo m, falls für alle r = r1, …, rφ(m) genau ein b ∈ B existiert mit b ≡ r (m). |
Die vollständigen Restsysteme modulo m sind genau die vollständigen Repräsentantensysteme der Äquivalenzrelation „modulo m“. Bei den reduzierten Restsystemen betrachten wir nur Repräsentanten, die teilerfremd zum Modul sind. Leicht einzusehen ist:
Satz (Äquivalenzen für Restsysteme)
Sei m ≥ 1. Dann gilt:
(a) | Zahlen a1, …, am bilden genau dann ein Restsystem modulo m, wenn sie paarweise inkongruent modulo m sind. |
(b) | Zahlen b1, …, bφ(m) bilden genau dann ein reduziertes Restsystem modulo m, wenn sie paarweise inkongruent und teilerfremd zu m sind. |
(c) | Ist A ein Restsystem modulo m, so ist B = { a ∈ A | (a, m) = 1 } ein reduziertes Restsystem modulo m. |
Wichtig für die folgenden Ergebnisse ist:
Satz (Umordnungssatz für Reste)
Sei m ≥ 1, und sei c teilerfremd zu m. Dann gilt:
(a) | { c0, c1, …, c(m − 1) } ist ein Restsystem modulo m. |
(b) | { cr1, cr2, …, crφ(m) } ist ein reduziertes Restsystem modulo m. |
Beweis
zu (a): Die m Zahlen c 0, …, c (m − 1) sind nach der Kürzungsregel für Kongruenzen wegen (c, m) = 1 paarweise inkongruent modulo m. Damit bilden sie ein Restsystem modulo m.
zu (b): Die φ(m) Zahlen c r1, … c rφ(m) sind nach der Kürzungsregel paarweise inkongruent und wegen (m, c) = 1 teilerfremd zu m. Damit bilden sie ein reduziertes Restsystem modulo m.
Die Sätze von Euler, Fermat und Wilson
Satz (Satz von Euler)
Sei m ≥ 1, und sei a teilerfremd zu m. Dann gilt aφ(m) ≡ 1 mod(m).
Beweis
Seien r1, …, rφ(m) die zu m teilerfremden Zahlen im Intervall { 1, …, m }. Nach dem Umordnungssatz für Reste gilt
r1 · r2 · … · rφ(m) ≡ ar1 · ar2 · … · arφ(m) (m).
Die Zusammenfassung der a-Faktoren auf der rechten Seite liefert
r1 · r2 · … · rφ(m) ≡ aφ(m) r1 · r2 · … · rφ(m) (m).
Da alle Zahlen r1, …, rφ(m) teilerfremd zu m sind, können wir sie nach der Kürzungsregel alle kürzen, sodass
1 ≡ aφ(m) (m).
Ist der Modul eine Primzahl p, so gilt φ(p) = p − 1 und wir erhalten:
Korollar (Satz von Fermat)
Sei p prim, und sei a kein Vielfaches von p. Dann gilt ap − 1 ≡ 1 mod(p).
Ein weiteres klassisches Ergebnis in diesem Umfeld ist:
Satz (Satz von Wilson)
Sei p prim. Dann gilt (p − 1)! ≡ −1 (p)
Beweis
Zunächst beobachten wir:
(+) Ist a ∈ ℤ und a2 ≡ 1 (m), so gilt a ≡ 1 oder a ≡ −1 (m).
Beweis von (+)
Aus a2 ≡ 1 (p) folgt a2 − 1 ≡ 0 (p) und damit
(a + 1)(a − 1) ≡ 0 (p).
Da p prim ist, ist a + 1 ≡ 0 (p) oder a − 1 ≡ 0 (p) nach der Kürzungsregel. Dies zeigt (+).
Sei nun a ∈ { 2, …, p − 2 }, und sei b ≡ ap − 2 (p) mit b ∈ { 0, …, p − 1 }. Nach dem Satz von Fermat und (+) ist ab ≡ ap − 1 ≡ 1 (m), b ∈ { 2, …, p − 2 } und a ≠ b. Damit können wir im Produkt 2 · … · (p − 2) die Faktoren paarweise zusammenfassen, sodass die entsprechenden Paarprodukte alle kongruent 1 modulo p sind. Folglich ist
(p − 1)! ≡ 1 · 2 · … · (p − 2) · (p − 1) ≡ 1 · 1 · … · 1 · (p − 1) ≡ p − 1 ≡ −1 (p).
Anwendungen
Wir diskutieren zwei Anwendungen der Ergebnisse. Die erste ist:
Satz (Lösung von Kongruenzen ersten Grades)
Sei m ≥ 1. Weiter seien a, b ∈ ℤ mit (a, m) = 1. Dann existiert modulo m genau eine Zahl x mit
a x ≡ b mod(m).
Genauer gilt
x ≡ aφ(m) − 1 b mod(m).(Lösungsformel für Kongruenzen ersten Grades)
Beweis
zur Existenz:
Wir setzen x = aφ(m) − 1 b. Dann gilt nach dem Satz von Euler:
a x ≡ a aφ(m) − 1 b ≡ aφ(m) b ≡ 1 b ≡ b (m).
zur Eindeutigkeit modulo m:
Seien x1, x2 Zahlen mit ax1 ≡ b (m) und ax2 ≡ b (m). Dann gilt
ax1 ≡ ax2 (m).
Wegen (a, m) = 1 gilt x1 ≡ x2 (m) nach der Kürzungsregel.
Die zweite Anwendung betrifft den Satz von Dirichlet über Primzahlen in arithmetischen Progressionen. Mit Hilfe der Kongruenzrelation können wir den Satz so formulieren:
Satz (Primzahlsatz von Dirichlet)
Seien a, m ≥ 1 teilerfremd. Dann gibt es unendlich viele Primzahlen p mit p ≡ a mod(m).
Mit Hilfe einer Variante des Beweises von Euklid der Unendlichkeit der Primzahlen konnten wir den Primzahlsatz von Dirichlet für den Spezialfall m = 4 und a = 3 vergleichsweise einfach beweisen. Der Satz von Fermat erlaubt mit einem trickreichen Argument den Beweis des Spezialfalls m = 4 und a = 1:
Satz (Primzahlen kongruent 1 modulo 4)
Es gibt unendlich viele Primzahlen p mit p ≡ 1 mod(4).
Beweis
Sei n ≥ 1 beliebig, und seien p1, …, pn Primzahlen mit pi ≡ 1 (4) für alle i ≤ n. Wir zeigen, dass es eine Primzahl p mit p ≡ 1 (4) gibt, die von allen Zahlen p1, …, pn verschieden ist. Hierzu setzen wir
a = 2p1 … pn und b = a2 + 1 = 4p12…pn2 + 1.
Dann ist b ≡ 1 (4). Ist b prim, so sind wir fertig. Andernfalls sei p ein Primteiler von b. Wegen b ≡ 0 (p) und b ≡ 1 (pi) für alle i ≤ n ist p von allen p1, …, pn verschieden. Wir zeigen, dass p ≡ 1 (4). Hierzu rechnen wir modulo p:
Da p ein Teiler von a2 + 1 ist, gilt a2 ≡ −1 (p). Hieraus folgt:
(+) a ≢ 1 (p), a ≢ −1 (p), a3 ≢ 1 (p), a4 ≡ 1 (p).
Die Zahl a ist kein Vielfaches von p, da sonst b ≡ 1 (p) gelten würde. Nach dem Satz von Fermat ist also ap − 1 ≡ 1 (p). Eine Division durch 4 mit Rest liefert ganze Zahlen q und r mit
p − 1 = q 4 + r und 0 ≤ r < 3.
Wegen a4 ≡ 1 (p) ist
1 ≡ ap − 1 ≡ aq4 + r ≡ aq4 ar ≡ (a4)q ar ≡ ar (p).
Da a, a2 und a3 nicht kongruent 1 modulo p sind, ist r = 0 und damit p − 1 durch 4 teilbar. Dies zeigt, dass p ≡ 1 (4).