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.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Hilfreiches

a ≡ b mod m ist äquivalent zu a = b + mk

Lösungsvorschlag von Aldinapoli

--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