TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 63

SS08 Beispiel 10

Man beweise folgende Regeln für das Rechnen mit Kongurenzen:

a) $a\equiv b\mod {m},c\equiv d\mod {m}\Rightarrow a+c\equiv b+d\mod {m}$

b) $a\equiv b\mod {m},c\equiv d\mod {m}\Rightarrow a\cdot c\equiv b\cdot d\mod {m}$

c) $a\cdot c\equiv b\cdot c\mod {m}\cdot c,c\neq 0\Rightarrow a\equiv b\mod {m}$

Hilfreiches

Restklassen

Restklassen

Restklassen modulo $m$:

${\overline {a}}=\lbrace a+km|k\in \mathbb {Z} \rbrace _{m}$

$a\equiv b\mod {m}$ kann man auch als $a=b+q\cdot m$ schreiben.

Lösungsvorschlag

Allgemeines:

Modulo teilt Werte in Restklassen durch Division mit dem Mod-Wert e, d.h. beide Werte haben bei der Division durch den Faktor m (Modulo) denselben Rest.

a $\equiv$ b mod m bedeutet daher bei Bestehen der Kongruenz, dass a/m und b/m denselben Rest haben. Daraus folgt, dass m | (b-c) gilt und somit m den Term (b-c) ohne Rest teilt (sonst nicht kongruent!).

Oder anders gesagt, eine kongruente Zahl a besteht aus m*k + r, wobei k eine beliebige Zahl ist und r der Rest. Und wenn die Reste gleich sind, liegt Kongruenz vor. Das könnte man für den Beweis verwenden und beim Nachweis der Äquivalenz jeweils alle m*k eliminieren, da ja nur die Reste für die Kongruenz von Bedeutung sind.

${\text{a) }}a\equiv b{\text{ (mod m)}},c\equiv d{\text{ (mod m)}},\Rightarrow a+c\equiv b+d{\text{ (mod m)}}$

a $\equiv$ b (mod m)  $\Rightarrow$  m*k1 + r1 $\equiv$ m*k2 + r1 (mod m) $\Rightarrow$ r1 = r1
c $\equiv$ d (mod m)  $\Rightarrow$  m*k3 + r2 $\equiv$ m*k4 + r2 (mod m) $\Rightarrow$ r2 = r2

Hapi

(a + c) $\equiv$  (b + d) (mod m) $\Rightarrow$ (m*k1 + m*k3 + r1 + r2) $\equiv$ (m*k2 + m*k4 + r1 +r2) (mod m)
   $\Rightarrow$  r1 + r2 = r1 + r2    somit Äquivalenz gegeben.

${\text{b) }}a\equiv b{\text{ (mod m)}},c\equiv d{\text{ (mod m)}},\Rightarrow ac\equiv bd{\text{ (mod m)}}$

a $\equiv$ b (mod m)  $\Rightarrow$  m*k1 + r1 $\equiv$ m*k2 + r1 (mod m) $\Rightarrow$ r1 = r1
c $\equiv$ d (mod m)  $\Rightarrow$  m*k3 + r2 $\equiv$ m*k4 + r2 (mod m) $\Rightarrow$ r2 = r2

(a * c) $\equiv$  (b * d) (mod m) $\Rightarrow$ (m*k1 + r1)* (m*k3 + r2) $\equiv$ (m*k2 +r1) * (m*k4 + r2) (mod m)  
     $\Rightarrow$  r1 * r2 = r1 * r2    somit Äquivalenz gegeben.

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

a $\equiv$ b (mod m)  $\Rightarrow$  m*k1 + r1 $\equiv$ m*k2 + r1 (mod m) $\Rightarrow$ r1 = r1
c $\equiv$ d (mod m)  $\Rightarrow$  m*k3 + r2 $\equiv$ m*k4 + r2 (mod m) $\Rightarrow$ r2 = r2

(a / c) $\equiv$  (b / d) (mod m) $\Rightarrow {\frac {(m*k1+r1)}{(m*k3+r2)}}$ $\equiv {\frac {(m*k2+r1)}{(m*k4+r2)}}$ (mod m) 
     $\Rightarrow$  r1 / r2 = r1 / r2    somit Äquivalenz gegeben.

Hapi

Lösungsvorschlag

Es gilt $b=a+q_{1}\cdot m$ und $d=c+q_{2}\cdot m$ bzw. $b-a=q_{1}\cdot m$ und $d-c=q_{2}\cdot m$.

Beispiel (a)

${\begin{aligned}b-a&=q_{1}\cdot m\\b-a+d-c&=q_{1}\cdot m+q_{2}\cdot m\\b+d-(a+c)&=(q_{1}+q_{2})\cdot m\\a+c&\equiv b+d\mod {m}\end{aligned}}$

Beispiel (b)

${\begin{aligned}b&=a+q_{1}\cdot m\\b\cdot d&=(a+q_{1}\cdot m)(c+q_{2}\cdot m)\\b\cdot d&=a\cdot c+a\cdot q_{2}\cdot m+c\cdot q_{1}\cdot m+q_{1}\cdot q_{2}\cdot m^{2}\\b\cdot d&=a\cdot c+(a\cdot q_{2}+c\cdot q_{1}+q_{1}\cdot q_{2}\cdot m)\cdot m\\a\cdot c&\equiv b\cdot d\mod {m}\end{aligned}}$

Beispiel (c)

${\begin{aligned}a\cdot c&\equiv b\cdot c\mod {m\cdot c}\\b\cdot c&=a\cdot c+q_{1}\cdot m\cdot c\\b&=a+q_{1}\cdot m\\a&\equiv b\mod {m}\end{aligned}}$