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

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

(a) $a\equiv b\mod m,\quad c\equiv d\mod m\Rightarrow a+c\equiv b+d\mod m$
(b) $a\equiv b\mod m,\quad c\equiv d\mod m\Rightarrow a\cdot c\equiv b\cdot d\mod m$

(c) $ac\equiv bc\mod mc,\quad c\neq 0\Rightarrow a\equiv b\mod m$

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

Lösungsvorschlag von Marco Z.

(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=k_a·m + r₁ und b = k_b·m + r₁ und c = k_c·m+r₂ und d = k_d·m+r₂

⇒ ac = (k_a·m+r₁)·(k_c·m+r₂) und bd = (k_b·m + r₁) · (k_d·m+r₂)

⇒ ac = k_a·k_c·m²+k_a·r₂·m+k_c·r₁·m+r₁·r₂ und bd = k_b·k_d·m²+k_b·r₂·m+k_d·r₁·m+r₁·r₂ [Hier wurde ausmultipliziert]

⇒ r_{1 ·} r₂ = r_{1 ·} r₂ (wenn wir alles durch m kürzbare entfernen)

Jetzt sehen wir fast alles ist durch m teilbar, somit Vielfache von m. Nur r₁ und r₂ 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

(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

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·k₁ + r, wobei m·c unser Modul ist, r der Rest und k₁ eine Unebkannte ∈ ℤ

b·c = m·c·k₂ + r

a·c - b·c = m·c·k₁ + r - (m·c·k₂ + r)

a·c - b·c = m·c·k₁ - m·c·k₂ \\ r kürzt sich weg

a·c - b·c = m·c·k \\ da k₁ und sind k₂ Unbekannte Koeffizienten ∈ ℤ von m·c, k₁·{term} - k₂·{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

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