Kongruenzsystem lösen Hilfe?
Meine Dozentin hat irgendwas gerechnet, aber ich weiß nicht, was sie hier genau gemacht hat.
4 + 3 = 3 mod 6
-4 + 4 + x = 3 - 4
x = -1
x = -1 = -1 * 6 + 5
= 5
L = {5} Z_6 eind. Lösung
oder
5x = 2 mod 12
5x = 2 = 2 + k * 12
x = (2+ 12 * k) / 5 = 2/3 = 14/5 = 3P / 5 = 50 / 5 = 10
L = {10} Z_12 eind. Lösung ggT(5; 12) = 1
Bitte Hilfe!
In der ersten Zeile ist dir ein Fehler passiert (die Gleichung ist falsch). Was sollte dort eigentlich stehen?
4 + x = 3 mod 6
1 Antwort
Zur ersten Aufgabe:
4 + x ≡ 3 (mod 6)
bedeutet, es existiert min. eine ganze Zahl z (x ist auch hier ganz) mit
4 + x = 6 z + 3
bzw. umgeformt
x = 6 z – 1.
Die einzige ganze Zahl z, sodass x aus Z_6 ist, ist z = 1 (also x = 5). Die gesamte Lösungsmenge wäre z = 1 + 6 t.
Das kannst du aber auch ganz einfach mit klassischen Umformen lösen, denn wenn
c + x ≡ d (mod m),
dann ist auch
c + x + r ≡ d + r (mod m),
denn wegen
c + x = 6 z + d
folgt
c + x + r = 6 z + d + r.
Also ist c + x + r mod m = d + r mod m und damit stimmt die Gleichung. (c, x, d, r seien ganze Zahlen bzw. m natürlich).
So kann man es noch leichter lösen:
4 + x ≡ 3 (mod 6) |–4
4 + x – 4 ≡ 3 – 4 (mod 6)
x ≡ –1 (mod 6)
Das ist äquivalent zu x = 6 z – 1. Die einzige Lösung in Z_6 ist für z = 1 dann x = 5.
Zur zweiten Aufgabe:
5 x ≡ 2 (mod 12)
bedeutet, es existiert min. eine ganze Zahl z (x ist auch eine ganze Zahl) mit
5 x = 12 z + 2
bzw. umgeformt
x = (12 z + 2) / 5.
Wir suchen alle z, sodass x eine ganze Zahl ist. Für z = 4 erhalten wir x = 10. Allerdings hätte auch z = 9 (x = 22) das lösen können. Genauer, alle z = 4 + 12 t mit ganzen t hätten die Gleichung lösen können.
Warum die Lösung eindeutig, kann ich mir nur erklären, weil 4 die einzige Lösung aus der Menge Z_12 = {0, 1, ..., 11} ist. Wobei man hier ja Restklassen betrachtet. Man hätte also genau so gut auch Z_12 = {12, 13, ..., 23} o. Ä. definieren können.
Man kann es aber auch anders lösen (ohne Raten).
Die Gleichung oben können wir auch umschreiben zu
2 = 5 x – 12 z.
Wenn du dich nun an den erweiterten euklidischen Algorithmus erinnerst, dann fällt dir ein, dass mit ggT(5, 12) = 1, der erweiterte Euklidalgorithmus ganze Zahlen a und b gibt, sodass 1 = 5 a + 12 b.
Wir haben nun aber nicht 1, sonder 2 dort stehen. Das ist aber kein Problem. Wir können die Gleichung einfach mit 2 multiplizieren und erhalten
2 = 5 (2 a) – 12 (–2 b).
Haben wir durch den erweiterten Euklidalgorithmus also zwei Zahlen a und b bekommen, ist unsere Lösung einfach x = 2 a mod 12. (Das "mod 12" nur, damit x in Z_12 liegt). z wäre dann z = –2 b mod 12.
Hier der erweiterte Euklidalgorithmus vorgerechnet:
12 = 2 • 5 + 2
5 = 2 • 2 + 1
2 = 2 • 1 + 0
also ggT(12, 5) = 1. Nun rückwärts einsetzen:
1 = 5 – 2 • 2
1 = 5 – 2 • (12 – 2 • 5)
also 1 = 5 • 5 + 12 • (–2).
Die Lösung ist also x = 2 • 5 mod 12 = 10. (z = –2 • (–2) mod 12 = 4.)