Difference between revisions of "TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 63"

From VoWi
Jump to navigation Jump to search
m
 
Line 9: Line 9:
 
</div>
 
</div>
  
==Hilfreiches==
+
==[[Vorlagen|Hilfreiches]]==
 
{{Restklassen}}
 
{{Restklassen}}
 
  
 
== Lösungsvorschlag ==
 
== Lösungsvorschlag ==

Revision as of 15:53, 3 November 2007

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

<amsmath>\text{a) } a \equiv b \text{ (mod m)}, c \equiv d \text{ (mod m)}, \Rightarrow a + c \equiv b + d \text{ (mod m)}</amsmath>

<amsmath>\text{b) } a \equiv b \text{ (mod m)}, c \equiv d \text{ (mod m)}, \Rightarrow ac \equiv bd \text{ (mod m)}</amsmath>

<amsmath>\text{c) } ac \equiv bc \text{ (mod mc)}, c \neq 0 \Rightarrow a \equiv b \text{ (mod m)}</amsmath>

Hilfreiches

Vorlage:Restklassen

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 daß a/m und b/m denselben Rest haben. Daraus folgt, daß 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.


<amsmath>\text{a) } a \equiv b \text{ (mod m)}, c \equiv d \text{ (mod m)}, \Rightarrow a + c \equiv b + d \text{ (mod m)}</amsmath>

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.


<amsmath>\text{b) } a \equiv b \text{ (mod m)}, c \equiv d \text{ (mod m)}, \Rightarrow ac \equiv bd \text{ (mod m)}</amsmath>

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.


<amsmath>\text{c) } ac \equiv bc \text{ (mod mc)}, c \neq 0 \Rightarrow a \equiv b \text{ (mod m)}</amsmath>

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