Lösen von Kongruenzen ersten Grades
Aus dem Satz von Euler erhalten wir eine Lösungsformel für Kongruenzen:
Satz (Lösung von Kongruenzen ersten Grades, I)
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.
Wir betrachten ein Beispiel für die Anwendung der Lösungsformel.
Beispiel
Wir lösen die Kongruenz
3x ≡ 5 (11).
Natürlich können wir alle Möglichkeiten x = 0, …, 10 durchprobieren. Da aber a = 3 und m = 11 teilerfremd sind, ist die Lösungsformel anwendbar. Es gilt φ(11) = 10. Wir setzen also
x = 3φ(m) − 1 b = 39 5.
Um eine Lösung im Intervall 0, …, 10 zu erhalten, ist es nicht nötig, 39 5 auszurechnen. Wir können x mit Hilfe der Kongruenzregeln schrittweise verkleinern, ohne große Zahlen berechnen zu müssen:
x ≡ 39 5 ≡ (33)3 5 ≡ 273 5 ≡ 53 5 ≡ 54 ≡ (25)2 ≡ 32 ≡ 9 (11).
Damit ist 9 die eindeutige Lösung der Kongruenz im Zahlenintervall von 0 bis 10. Zur Probe rechnen wir
3 · 9 ≡ 27 ≡ 5 (11).
Lösungstafel der Kongruenz ax ≡ b (7) für a, b = 1, …, 6
Lösungstafel der Kongruenz ax ≡ b (13) für a, b = 1, …, 12
Nichteindeutig lösbare Kongruenzen ersten Grades
Ist die Bedingung (a, m) = 1 für eine Kongruenz ax ≡ b (m) verletzt, ist die Lösungstheorie komplizierter. Hierzu ein Beispiel:
Beispiel: Mehrere oder keine Lösungen
Wir betrachten die Kongruenz 4x ≡ 6 (10). Es gilt g = (4, 10) = 2, sodass die Lösungsformel nicht anwendbar ist. Wir berechnen:
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
4x | 0 | 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 |
mod (10) | 0 | 4 | 8 | 2 | 6 | 0 | 4 | 8 | 2 | 6 |
Der Tabelle entnehmen wir die Lösungen x1 = 4 und x2 = 9. Allgemein gilt: Ist b ungerade, so besitzt die Kongruenz keine Lösungen. Ist b gerade, so gibt modulo 10 genau 2 Lösungen von 4x ≡ b (10), die den Abstand 5 voneinander haben. Es gilt 5 = 10/2 = m/g.
Für dieses Beispiel gilt also
Abstand zweier Lösungen = ModulAnzahl der Lösungen = Modul(a, m)
Diese Zusammenhänge sind kein Zufall. Allgemein gilt folgender Satz, dessen Beweis wir dem Leser als Übung überlassen:
Satz (Lösung von Kongruenzen ersten Grades, II)
Seien a, b, m ∈ ℤ mit m ≥ 1. Weiter sei g = (a, m) ≥ 2. Dann gilt:
(a) | Ist g kein Teiler von b, so hat die Kongruenz ax ≡ b (m) keine Lösung. |
(b) | Ist g ein Teiler von b, so seien b* = b/g, m* = m/g, a* = a/g, x1 = „die eindeutige Lösung von a*x ≡ b* (m*) in 0, …, m* − 1“. Dann hat die Kongruenz ax ≡ b (m) modulo m genau die g Lösungen x1, x2 = x1 + m*, …, xg = x1 + (g − 1) m*. |
In den folgenden Diagrammen notieren wir die Lösungen im Fall (b) in der kompakten Form x1 + cm*. Zum Beispiel hat die Kongruenz 4x ≡ 8 (12) in dieser Notation die Lösung 2 + 3c. Mit g = (4, 12) = 4 ergeben sich die vier Lösungen 2, 5, 8, 11 im Intervall 0, …, 11.
Lösungstafel der Kongruenz ax ≡ b (6) für a, b = 1, …, 6
Lösungstafel der Kongruenz ax ≡ b (12) für a, b = 1, …, 12