Kryptologie/Division mit Rest

Einleitung

Wir haben in die Kongruenz in der zugehörigen Lerneinheit als mathematische Beziehung, die die Differenz zweier ganzen Zahlen misst und dieser Differenz eine natürliche Zahl zuordnet, deren Vielfaches der Differenz entspricht, beschrieben. Wir können aber auch sagen, dass die zwei Zahlen kongruent modulo einer natürlichen Zahl sind, wenn beide Zahlen bei Division durch die natürliche Zahl den gleichen Rest aufweisen. Wir definieren hierfür die Division mit Rest und zeigen am Ende, dass folgende Äquivalenz gilt:

Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$, dann gilt $a\equiv b{\bmod {m}}\Leftrightarrow a=m\cdot k+b$ mit $k\in \mathbb {Z}$.

Division mit Rest

Satz Division mit Rest

Seien $a,b\in \mathbb {Z}$ und $b>0$, dann gibt es eindeutig bestimmte Zahlen $k\in \mathbb {Z}$ und $r\in \mathbb {N}$, für die gilt:

$a=k\cdot b+r$ mit $0\leq r<b$.

Beweis Division mit Rest

Voraussetzung

$a,b\in \mathbb {Z}$ und $b>0$

Zu zeigen

• Es existieren $k\in \mathbb {Z}$ und $r\in \mathbb {N}$, sodass gilt: $a=k\cdot b+r$ mit $0\leq r<b$,
• $k\in \mathbb {Z}$ und $r\in \mathbb {N}$ sind eindeutig

Beweis

Zunächst betrachten wir die Menge$M=\{a-xb\mid x\in \mathbb {Z} ,a-xb\geq 0\}$ und zeigen, dass diese Menge nicht leer ist. Wir suchen zu diesem Zweck ein $x\in \mathbb {Z}$, sodass $a-xb\geq 0$.

Wegen $b>0$ gilt $|a|b\geq |a|$ und wir können folgern

$a-(-|a|)b=a+|a|b\geq a+|a|\geq 0$.

Nehmen wir nun an, dass $x=-|a|$, dann gilt

$a-xb\in M$

und somit ist $M$ also nicht leer.

Wir nennen nun $r$ das kleinste Element der Menge $M$. Nach Definition von $M$ erhalten wir

$r=a-kb$ mit $0\leq r$ und $k\in \mathbb {Z}$.

Nun zeigen wir, dass $r<b$ durch Widerspruch.

Sei also $r\geq b$, dann gilt

$r-b\geq 0$

und

$r-b=(a-kb)-b=a-(k+1)b\in M$.

Dann ist $r-b\in M$. Dies ist ein Widerspruch, da $r-b<r$, was im Widersprich dazu steht, dass wir $r$ als kleinstes Element von $M$ gewählt haben. Folglich ist $r<b$.

Wir müssen nun noch die Eindeutigkeit von $k$ und $r$ zeigen.

Wir zeigen erneut durch Widerspruch, dass es keine zwei verschiedene Konstruktionsmöglichkeiten von $a$ mit $b$ gibt.

Sei also $a=kb+r=jb+z$ mit $k,j\in \mathbb {Z}$ und $r,z\in \mathbb {N}$, wobei $0\leq r<b$ und $0\leq z<b$.

Dann gilt

$|z-r|=b|k-j|$

und

$-b<z-r<b$

$\Leftrightarrow |z-r|<b$.

Setzt man dies in $|z-r|=b|k-j|$ ein, erhält man

$0\leq |k-j|<1$.

Da jedoch $k,j\in \mathbb {Z}$, muss gelten $k=j$ und es folgt

$|z-r|=b\cdot 0=0$.

Es gilt also auch $z=r$ und wir haben die Eindeutigkeit gezeigt.■

Lernaufgabe

Aufgabe

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

Beweisen Sie, dass folgende Äquivalenz gilt: $a\equiv b{\bmod {m}}\Leftrightarrow a=m\cdot k+b$ mit $k\in \mathbb {Z}$.

Lösung
Seien $a,b\in \mathbb {Z}$ und $m\in \mathbb {N}$. $a\equiv b{\bmod {m}}$ $\Leftrightarrow m\mid (a-b)$, nach Definition der Kongruenz $\Leftrightarrow m\cdot k=(a-b)$ mit $k\in \mathbb {Z}$ nach Definition der Teilbarkeit $\Leftrightarrow a=m\cdot k+b$■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4.3: Kongruenzen	4.4: Division mit Rest	4.5: Restklassen