Worksheet

Druckversion

Definition: Division mit Rest

Vervollständige die Definition.

Es sei $a \ \in \ \mathbb{Z}$ und $b \ \in \ \mathbb{N}$.

Trage hier noch weitere Beispiele ein.

$27 =\ q\ \cdot \ 8 \ + \ r<br /> q = \ 27 \ div \ 8 \ = 3<br /> r = \ 27 \ mod \ 8 \ = 3<br />$

$-14 =\ q\ \cdot \ 9 \ + \ r<br /> q = \ -14 \ div \ 9 \ = <br /> r = \ -14 \ mod \ 9 = <br />$

Definition: Kongruenz

Vervollständige die Definition.

Es sei $m \ \in \ \mathbb{N}$ und $a,b \ \in \ \mathbb{Z}$.

Formuliere die Definition in anderer Form bzw. in eigenen Worten.

Satz zur Kongruenz

Vervollständige den Beweis und notiere die jeweiligen Begründungen.

$a \equiv b\ mod\ m \Leftrightarrow m |(a-b)$

Beweis in zwei Richtungen:

"$\Rightarrow$" (die eine Richtung)

Es gilt nach Voraussetzung $a \equiv b\ mod\ m$
Zu zeigen: $m |(a-b)$
$a \equiv b\ mod\ m$ (Voraussetzung)
$\Rightarrow \ a \ mod\ m = b\ mod\ m$ (Def. Kongruenz)

$\Rightarrow \exist q_1, q_2 \in \mathbb {Z}$ mit

"$\Leftarrow$" (Rückrichtung)

Es gelte: $m |(a-b)$
zu zeigen: $a \equiv b\ mod\ m$
$m |(a-b)\Rightarrow \exist q_1, q_2, r_1, r_2 \in \mathbb {Z}$: $a = m \cdot q_1 + r_1$ und $b = m \cdot q_2 + r_2$
$\Rightarrow m| \Big((q_1 \cdot m + r_1) - (q_2 \cdot m + r_2)\Big)$

Kongruenz als Äquivalenzrelation

Satz: Kongruenz modulo m ist eine Äquivalenzrelation.

zu zeigen: Die Kongruenzrelation ist...
(1) reflexiv: $\forall a \in \mathbb {Z}$: $a \equiv b\ mod\ m$
(2) symmetrisch: $\forall a,b \in \mathbb {Z}$: $a \equiv b\ mod\ m \Rightarrow b \equiv a\ mod\ m$
(3) transitiv: $\forall a,b,c \in \mathbb {Z}$: $a \equiv b\ mod\ m \ \wedge \ b \equiv c\ mod\ m \Rightarrow a \equiv c\ mod\ m$

Trage hier die zugehörigen Beweise ein.

Rechnen mit Kongruenzen

Satz: Seien $a,b,c,d \in \mathbb {Z}$ und $m \in \mathbb{N}$ mit $a \equiv b\ mod\ m\ \wedge\ c \equiv d\ mod\ m$ dann gilt...

(1) $a+c \equiv b+d\ mod\ m$

Beweis:
$m|(a-b) \wedge m|(c-d)$
$\Rightarrow m|(a-b)+(c-d)$
$\Rightarrow m|a+c-b-d$
$\Rightarrow m|(a+c)-(b+d)$

Führe die Beweise zu (2) und (3)

(2) $a-c \equiv b-d\ mod\ m$
Beweis:





(3) $a \cdot c \equiv b\cdot d\ mod\ m$
Beweis:

Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!