Worksheet

Druckversion

Definition Restklassen

Es sei $a \ \in \ \mathbb{Z}$ und $m \ \in \ \mathbb{N}$.
Jede Menge

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:

Satz zur 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 {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}$

Formuliere diese Folgerung ganz allgemein in eigenen Worten!

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!