Kryptologie/Teilbarkeit und Teilerfremdheit

Einleitung

Die Teilbarkeit ist eine grundlegende mathematische Beziehung zwischen zwei Zahlen, auf die sich beispielsweise die Kongruenz und viele weitere wichtige Sätze dieses Kurses stützen. Dies gilt sowohl für die Lerninhalte des Caesar- als auch für die des RSA-Kryptosystems.

Teilbarkeit

Definition Teilbarkeit

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

$a$ teilt $b$ genau dann, wenn es eine Zahl $k\in \mathbb{Z}$ gibt, für die $a\cdot k=b$ ist. Wir sagen dann „$a$ ist Teiler von $b$“, „$a$ teilt $b$“ oder „$b$ ist teilbar durch $a$“ und schreiben formal:

$a\mid b$.

Für das Gegenteil, wenn es also keine Zahl $k\in \mathbb{Z}$ gibt, für die $a\cdot k=b$ ist, sagen wir „$a$ ist kein Teiler von $b$“, „$a$ teilt $b$ nicht“ oder „$b$ ist nicht teilbar durch $a$“ und schreiben:

$a\nmid b$.

Beispiel

$2\mid 6$ bzw. $2$ ist ein Teiler von $6$, da $2\cdot 3=6$.

$4\mid ̸6$, da $1\cdot 4=4<6$ und $2\cdot 4=8>6$

Bemerkung: Wir zeigen nun einige wichtige Eigenschaften der Teilbarkeit, die wir später in Beweisen benötigen werden.

Lemma

Seien $a,b,c,d,m\in \mathbb{Z}$, dann gilt:

$(1)$: $a\mid b\iff a\mid (-b)$

$(2)$: $a\mid 1\iff a=\pm 1$

$(3)$: $a\mid b$ und $a\mid c\Rightarrow a\mid (bs+ct)$ für beliebige $s,t\in \mathbb{Z}$

$(4)$: $m\mid (a-b)\Rightarrow m\mid (-a+b)$

Beweis Lemma

Zu $(1)$:

Teilbarkeit
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $k$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.

Voraussetzung

$a,b\in \mathbb{Z}$ und $a\mid b$

Zu zeigen

$a\mid b\iff a\mid (-b)$

Beweis

Nach Voraussetzung gilt

$a\mid b$

$\iff b=a\cdot k$, für ein $k\in \mathbb{Z}$ und nach Definition Teilbarkeit

$\iff -b=-(a\cdot k)$

$\iff -b=a\cdot (-k)$

$\iff a\mid (-b)$, nach Definition Teilbarkeit■

Zu $(2)$:

Voraussetzung

$a\in \mathbb{Z}$ und $a\mid 1$

Zu zeigen

Teilbarkeit
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $k$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.

$a\mid 1\iff a=\pm 1$

Beweis

Nach Voraussetzung gilt:

$a\mid 1$

$\iff a\cdot k=1$, da nach Definition Teilbarkeit $a\cdot k=1$ für ein $k\in \mathbb{Z}$

Gesucht sind nun $a,k\in \mathbb{Z}$, für $a\cdot k=1$ gilt.

Dies sind genau $a=k=\pm 1$■

Zu $(3)$:

Voraussetzung

$a,b,c\in \mathbb{Z}$, $a\mid b$ und $a\mid c$

Zu zeigen

Teilbarkeit
Teilbarkeit
Eine ganze Zahl $a$ teilt eine ganze Zahl $b$ genau dann, wenn es eine ganze Zahl $k$ gibt, für die $a\cdot k=b$ ist. Wir schreiben $a\mid b$.

$a\mid b$ und $a\mid c\Rightarrow a\mid (bs+ct)$ für beliebige $s,t\in \mathbb{Z}$

Beweis

Aus der Definition der Teilbarkeit folgt für $a\mid b$ bzw. $a\mid c$

$ax=b$ für $x\in \mathbb{Z}$

bzw.

$ay=c$ für $y\in \mathbb{Z}$.

Wir können die beiden Gleichungen jeweils mit einer beliebigen ganzen Zahl $s$ bzw. $t$ multiplizieren und erhalten

$axs=bs$

bzw.

$ayt=ct$

Wir addieren $ayt$ in der Gleichung $axs=bs$ und erhalten

$axs+ayt=bs+ayt$

$\iff axs+ayt=bs+ct$, da $ayt=ct$

$\iff a(xs+yt)=bs+ct$

Da $xs+yt$ eine ganze Zahl ist, gilt nach Definition der Teilbarkeit

$a\mid (bs+ct)$■

Zu $(4)$:

Siehe Lernaufgabe.

Teilerfremdheit

Definition Teilerfremdheit

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

$a$ und $b$, wobei mindestens $a$ oder $b$ ungleich Null, heißen teilerfremd, wenn es keine Zahlen $k\in \mathbb{Z}$ außer $k=\pm 1$ gibt, die beide Zahlen teilt. Wir sagen dann „$a$ und $b$ sind teilerfremd".

Betrachten wir mehr als zwei Zahlen, dann nennen wir diese paarweise teilerfremd, wenn je zwei beliebige von diesen Zahlen zueinander teilerfremd sind.

Größte gemeinsame Teiler
Größte gemeinsame Teiler
Seien $a,b\in \mathbb{Z}$, wobei mindestens eine der beiden Zahlen ungleich Null. Wir bezeichnen $d:=ggT(a,b)$ mit $d\in \mathbb{N}$ als den größten gemeinsamen Teiler der Zahlen $a$ und $b$, falls gilt: $(1)$: $d\mid a$ und $d\mid b$ und $(2)$: Für alle $c\in \mathbb{Z}$ mit $c\mid a$ und $c\mid b$ gilt $c\le d$.

Alternative

Ist der größte gemeinsame Teiler bekannt, so kann man die Definition auch anders formulieren:

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

$a$ und $b$, wobei mindestens einer der beiden Zahlen ungleich Null ist, heißen teilerfremd, wenn $ggT(a,b)=1$.

Bemerkung: Besonders die alternative Definition wird uns in anderen Lerneinheiten von großem Nutzen sein.

Lernaufgabe

Aufgabe

Optionaler Hinweis
Nutzen Sie das Lemma zur Teilbarkeit: $(1)$
Seien $a,b,c,d,m\in \mathbb{Z}$, dann gilt: $a\mid b\iff a\mid (-b)$

Seien $a,b,m\in \mathbb{Z}$ und $m\mid (a-b)$.

Beweisen Sie, dass gilt: $m\mid (a-b)\Rightarrow m\mid (-a+b)$.

Lösung
Voraussetzung $a,b,m\in \mathbb{Z}$ und $m\mid (a-b)$ Zu zeigen $m\mid (a-b)\Rightarrow m\mid (-a+b)$ Beweis Nach Voraussetzung gilt $m\mid (a-b)$ $\Rightarrow m\mid d$, für $d=a-b$ mit $d\in \mathbb{Z}$ $\Rightarrow m\mid -d$, nach $(1)$ des Lemmas der Teilbarkeit $\Rightarrow m\mid -(a-b)$, nach $d=a-b$ $\Rightarrow m\mid (-a+b)$■

Lernempfehlung

Kursübersicht

Übergeordnete Lerneinheit
4: Caesar-Verschlüsselungsverfahren
Vorherige Lerneinheit	Aktuelle Lerneinheit	Empfohlene Lerneinheit
4: Caesar-Verschlüsselungsverfahren	4.1: Teilbarkeit und Teilerfremdheit	4.2: Größte gemeinsame Teiler