TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 70

Aus VoWi
Zur Navigation springen Zur Suche springen

Man beweise die folgenden Regeln für das Rechnen mit Kongruenzen:

(a)
(b)

(c)

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


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