TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 70
Man beweise die folgenden Regeln für das Rechnen mit Kongruenzen:
(a)
(b)(c)
Hilfreiches[Bearbeiten | Quelltext bearbeiten]
Lösungsvorschlag von Marco Z.[Bearbeiten | Quelltext bearbeiten]
(a) a ≡ b mod m, c ≡ d mod m ⇒ a + c ≡ b + d mod m
k ist ein beliebiges Vielfaches
a ≡ b mod m, c ≡ d mod m ⇒ a-b ≡ k1 · m und c-d ≡ k2 · m
⇒ a-b + c-d = (k1 + k2) · m
⇒ a+c - (b+d) = (k1+ k2) · m [Hier wurde nur umgeformt]
Durch k1+k2 ∈ Z lt a ≡ b mod m ⇐⇒ ∃k ∈ Z: a-b = k·m
können wir auch schreiben:
a + c ≡ b + d mod m
(b) a ≡ b mod m, c ≡ d mod m ⇒ a · c ≡ b · d mod m
k ist wieder ein beliebiges Vielfaches, r ist ein Rest, m ist das modulo
a=ka·m + r1 und b = kb·m + r1 und c = kc·m+r2 und d = kd·m+r2
⇒ ac = (ka·m+r1)·(kc·m+r2) und bd = (kb·m + r1) · (kd·m+r2)
⇒ ac = ka·kc·m²+ka·r2·m+kc·r1·m+r1·r2 und bd = kb·kd·m²+kb·r2·m+kd·r1·m+r1·r2 [Hier wurde ausmultipliziert]
⇒ r1 · r2 = r1 · r2 (wenn wir alles durch m kürzbare entfernen)
Jetzt sehen wir fast alles ist durch m teilbar, somit Vielfache von m. Nur r1 und r2 bestimmen somit die Rechnung. Ergo:
a · c ≡ b · d mod m
Lösungsansatz von ManuDesu ist besser für c)
Lösungsvorschlag Beispiel a von ManuDesu[Bearbeiten | Quelltext bearbeiten]
(a) a ≡ b mod m, c ≡ d mod m ⇒ a + c ≡ b + d mod m
Wenn a und b durch m denselben Rest ergeben, wissen wir, dass m teilt b-a u. a-b.
Nennen wir die Differenz aus a-b: x und die Differenz aus c-d: y.
Da beide Differenzen durch dieselbe Zahl teilbar sind, muss auch deren Summe (x+y) durch m teilbar sein.
Sprich wir schreiben: (a-b) + (c-d) = a + c - (b + d) (es wurde nur umgeformt).
a + c - (b + d) --> a + c ≡ b + d
Lösungsvorschlag von Tesserakt[Bearbeiten | Quelltext bearbeiten]
Ergänzung zu Bsp. c) a·c ≡ b·c mod m·c, c ≠ 0 ⇒ a ≡ b mod m
da a·c ≡ b·c mod m·c wissen wir, dass a·c - b·c durch m teilbar sein muss oder m·c | a·c - b·c
Für a ≡ b mod m gilt synchron dazu m | a - b
a·c = m·c·k1 + r, wobei m·c unser Modul ist, r der Rest und k1 eine Unebkannte ∈ ℤ
b·c = m·c·k2 + r
a·c - b·c = m·c·k1 + r - (m·c·k2 + r)
a·c - b·c = m·c·k1 - m·c·k2 \\ r kürzt sich weg
a·c - b·c = m·c·k \\ da k1 und sind k2 Unbekannte Koeffizienten ∈ ℤ von m·c, k1·{term} - k2·{term} lässt sich also zu k·{term} zusammenfassen mit k ∈ ℤ
c·(a - b) = m·c·k \\ wir können c herausheben
a - b = m·k \\ c lässt sich wegkürzen
In der Form a - b = m·k erkennen wir, dass a-b ebenfalls ein Vielfaches von m sein muss. Da m | a - b gilt können wir davon auf a ≡ b mod m zurückschließen.
Lösungsvorschlag von Sanso[Bearbeiten | Quelltext bearbeiten]
Ergänzung zu Bsp. c) a·c ≡ b·c mod m·c, c ≠ 0 ⇒ a ≡ b mod m
da a·c ≡ b·c mod m·c wissen wir, dass a·c - b·c durch m teilbar sein muss oder m·c | a·c - b·c
also gilt auch a*c - b*c = k * m * c | : c wir rechnen durch c und erhalten a - b = k * m
wenn a - b = k * m dann gilt auch m | a - b also a ≡ b mod m