TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 62
a) Beweisen Sie, dass man in einer Kongruenz einen gemeinsamen Faktor der Kongruenzgleichung und des Moduls kurzen kann, d.h. für c ≠ 0 folgt aus ac ≡ bc mod mc, dass a ≡ b mod m. Gilt auch umgekehrt, dass aus a ≡ b mod m immer ac ≡ bc mod mc folgt, falls?
b) Beim Rechnen mit Kongruenzen dürfen Zahlen immer durch kongruente Zahlen ersetzt werden, d.h. falls a + b ≡ c mod m und b ≡ d mod m, dann gilt a + d ≡ c mod m.
Hilfreiches[Bearbeiten | Quelltext bearbeiten]
a ≡ b mod m ist äquivalent zu a = b + mk
Lösungsvorschlag von Aldinapoli[Bearbeiten | Quelltext bearbeiten]
--Aldinapoli 01:38, 17. Feb. 2025 (CET)
a)
Mithilfe der unter "Hilfreiches" angeführte Äquivalenz kann man folgende Umformung durchführen:
ac ≡ bc mod mc
<=> ac = bc + mck | : c
<=> a = b + mk
<=> a ≡ b mod m
Also ist ac ≡ bc mod mc <=> a ≡ b mod m
- - - - -
Der Beweis für die zweite Frage ist gleich, nur geht er diesmal in die andere Richtung
a ≡ b mod m
<=> a = b + mk | * c
<=> ac = bc + mck
<=> ac ≡ bc mod mc
2)
Es ist zu zeigen: (a + b ≡ c mod m ∧ b ≡ d mod m) → a + d ≡ c mod m
Aus der vorher etablierten Äquivalenz kann man b folgendermaßen definieren:
b = d + mk
wenn man also für b in a + b ≡ c mod m einsetzt, erhält man:
a + d + mk ≡ c mod m
da wir uns im Modul m befinden, fällt sämtliches Vielfaches von m weg, da m % m = 0 ist, also steht am Ende:
a + d ≡ c mod m