Worksheet

Druckversion

Definition Restklassen

Es sei $a \ \in \ \mathbb{Z}$ und $m \ \in \ \mathbb{N}$.
Jede Menge $\overline{a} := \{x \in \mathbb{Z}| x \equiv a\ mod\ m\}$ bezeichnet man als Restklasse modulo m.
Jedes $x \in \overline {a}$ heißt Repräsentant von $\overline {a}$.
Die Menge aller Restklassen modulo m bezeichnet man als $R_m$.

Beispiel:
$R_5 = \{\overline {0},\overline {1},\overline {2},\overline {3},\overline {4}\} = \{ \{...-5,0,5,10,...\}, \{-4,1,6,...\},...\}$

Satz zu Restklassen

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

Seien $a,b \in \mathbb {Z}$ und $m \in \mathbb {N}$.
Dann gilt:$a \equiv b\ mod\ m \Leftrightarrow \overline {a} = \overline {b}$

Beweis in zwei Richtungen:

"$\Rightarrow$" (die eine Richtung)

Es gilt nach Voraussetzung $a \equiv b\ mod\ m$
Zu zeigen: $\overline {a} = \overline {b}$.
Um die Gleichheit zweier Mengen zu zeigen, benutzt man oft die Antisymmetrie der Teilmengen-Relation. Man zeigt also
(1) $\overline {a} \subseteq \overline {b}$ und (2) $\overline {b} \subseteq \overline {a}$

zu (1): zeige $\overline {a} \subseteq \overline {b}$
Sei $x \in \overline {a}$, dann gilt $x \equiv a\ mod\ m$ (Definition Restklasse).
Außerdem gilt $a \equiv b\ mod\ m$ (_____________________________)
$\Rightarrow x \equiv b\ mod\ m$ (_____________________________)
$\Rightarrow x \in \overline {b}$ (_____________________________)
$\Rightarrow \overline {a} \subseteq \overline {b}$ (_____________________________)

zu (2): zeige $\overline {b} \subseteq \overline {a}$

"$\Leftarrow$" (Rückrichtung)

Es gelte: $\overline {a} = \overline {b}$
zu zeigen: $a \equiv b\ mod\ m$

$a \in \overline {a} \Rightarrow a \in \overline {b} \Rightarrow a \equiv b \ mod \ m$

$b \in \overline {b} \Rightarrow$

Definition: Restklassenaddition

Seien $\overline {a} \ ,\ \overline {b}\ \in \ R_m$.
Dann ist $\overline {a}\ \oplus\ \overline {b}\ =\ \overline {a+b}$

Beispiele:

$\overline {2}\ \oplus\ \overline {3}\ =\ \overline {2+3}\ =\ \overline {5}\ =\ \overline {0}$

$\overline {1022}\ \oplus\ \overline {753}\ =\ \overline {1775}\ =\ \overline {0}$

$\overline {927}\ \oplus\ \overline {1953}\ =$

$\overline {331}\ \oplus\ \overline {443}\ =$

$\overline {78}\ \oplus\ \overline {1113}\ =$

Definition: Restklassenmultiplikation

Seien $\overline {a}\ ,\ \overline {b}\ \in\ R_m$.

Dann ist $\overline {a}\ \otimes\ \overline {b}\ =\ \overline {a \ \cdot\ b}$

Beispiele:
$\overline {17}\ \otimes\ \overline {12}\ =\overline {17\ \cdot\ 12}\ =\ \overline {204}\ =\ \overline {4}$

$\overline {83}\ \otimes\ \overline {107}\ =\overline {83\ \cdot\ 107}\ =\ \overline {8881}\ =\ \overline {6}\ =\ \overline {1}$

$\overline {14}\ \otimes\ \overline {6}\ =$

$\overline {23}\ \otimes\ \overline {9}\ =$

Folgerung aus bisher bewiesenen Sätzen und Definitionen

Aus den Sätzen $a \equiv b\ mod\ m\ \wedge\ c \equiv d\ mod\ m\ \Rightarrow\ a+c \equiv b+d\ mod\ m$ bzw. $a \equiv b\ mod\ m\ \wedge\ c \equiv d\ mod\ m\ \Rightarrow\ a \cdot c \equiv b\cdot d\ mod\ m$

und $a \equiv b\ mod\ m \Leftrightarrow \overline {a} = \overline {b}\$und den Definitionen der Restklassenaddition und Restklassenmultiplikation kann man nun folgern, dass...

$\overline {a}\ =\ \overline {b}\ \wedge\ \overline {c}\ =\ \overline {d}\ \Rightarrow\ \overline {a\ +\ c}\ =\ \overline {b\ +\ d}\ \Rightarrow \overline {a}\ \oplus\ \overline {c}\ =\ \overline {b}\ \oplus\ \overline {d}$

$\overline {a}\ =\ \overline {b}\ \wedge\ \overline {c}\ =\ \overline {d}\ \Rightarrow\ \overline {a\ \cdot\ c}\ =\ \overline {b\ \cdot\ d}\ \Rightarrow \overline {a}\ \otimes\ \overline {c}\ =\ \overline {b}\ \otimes\ \overline {d}$

Beispiele:
$\overline {1022}\ =\ \overline {2}\ \wedge\ \overline {753}\ =\ \overline {3}\ \Rightarrow\ \overline {1022\ +\ 753}\ =\ \overline {2\ +\ 3}\ \Rightarrow\ \overline {1022}\ \oplus\ \overline {753}=\ \overline {2}\ \oplus\ \overline {3}$

$\overline {927}\ =\ \overline {2}\ \wedge\ \overline {1951}\ =\ \overline {1}\ \Rightarrow$

$\overline {334}\ =\ \ \ \ \ \ \ \wedge\ \overline {99367}\ =\ \ \ \ \ \ \ \Rightarrow$

$\overline {17}\ =\ \overline {2}\ \wedge\ \overline {12}\ =\ \overline {2}\ \Rightarrow\ \overline {17\ \cdot\ 12}\ =\ \overline {2\ \cdot\ 2}\ \Rightarrow\ \overline {17}\ \otimes\ \overline {12}=\ \overline {2}\ \otimes\ \overline {2}$

$\overline {99341}\ =\ \overline {1}\ \wedge\ \overline {42}\ =\ \overline {2}\ \Rightarrow$

$\overline {579}\ =\ \ \ \ \ \ \ \wedge\ \overline {5683}\ =\ \ \ \ \ \ \ \Rightarrow$

Formuliere diese Folgerung ganz allgemein in eigenen Worten!

Quersummenregel

Die Quersummenregel gilt für die Division durch 3 und 9 und besagt: Wenn die Summe der einzelnen Ziffern einer Zahl durch 3 oder 9 teilbar ist, dann ist die Zahl selbst durch 3 oder 9 teilbar.

Beispiel:
Quersumme von $2781 = Q(2781) = 2 + 7 + 8 + 1 = 18\$
9 teilt 18 $\Rightarrow$ 9 teilt 2781

$2781\ \equiv\ 2\ \cdot\ 1000\ +\ 7 \cdot\ 100\ +$

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!