ggT & kgV

Primfaktorzerlegungen spielen auch beim Bestimmen des ggT (grösster gemeinsamer Teiler) und des kgV (kleinstes gemeinsames Vielfaches) zweier natürlicher Zahlen $a$ und $b$ eine wichtige Rolle.

Exercise 1: kgV und ggT

Bestimme das kgV und den ggT der Zahlen $153'900$ und $180'600$ .

Solution

Es ist

\begin{align*} 153'900 &= 2^2\cdot3^4\cdot5^2\cdot19\\ 180'600 &= 2^3\cdot3\cdot5^2\cdot7\cdot43 \end{align*}

und daher $\text{ggT}(180'600, 153'900)=2^2\cdot3\cdot5^2$ und $\text{kgV}(180'600, 153'900)=2^3\cdot3^4\cdot5^2\cdot7\cdot19\cdot43$ .

Note 1

Bei grossen Zahlen ist die Methode der Primfaktorzerlegung jedoch oft sehr aufwändig oder praktisch nicht durchführbar.

Der Euklid'sche Algorithmus

Note 2: Euklidischer Algorithmus

Zur Bestimmung des ggT zweier Zahlen $a$ und $b$ verwendet man am effizientesten den Euklidischen Algorithmus.

Als Beispiel betrachten wir die Zahlen $153'900$ und $180'600$ . Zunächst wird die grössere durch die kleinere Zahl geteilt und der Rest bestimmt. Anschliessend teilt man die kleinere Zahl durch diesen Rest und berechnet den neün Rest. Dieses Verfahren setzt man so lange fort, bis der Rest gleich null ist. Der letzte von null verschiedene Rest ist der ggT.
(Euklidischer Algorithmus kommentiert)

Solution

\begin{align*} 180'600 &= 153'900 \cdot 1 + 26'700 \\ 153'900 &= 26'700 \cdot 5 + 20'400 \\ 26'700 &= 20'400 \cdot 1 + 6300 \\ 20'400 &= 6300 \cdot 3 + 1500 \\ 6300 &= 1500 \cdot 4 + 300 \\ 1500 &= 300 \cdot 5 + 0 \end{align*}

Damit ist $\mathrm{ggT}(153'900,180'600) = 300$ .

Exercise 2: 🧩

Zeige, dass der Euklid'sche Algorithmus stets den ggT der beiden Zahlen liefert.

Solution

Der Beweis wird im Satz unten geführt.

Theorem 1: Euklid'scher Algorithmus

Der Euklid'sche Algorithmus berechnet den grössten gemeinsamen Teiler $\operatorname{ggT}(a,b)$ zweier ganzer Zahlen $a$ und $b$ $(a>b)$ :

Teile $a$ durch $b$ und bestimme den Rest $r$ :

a = q\cdot b + r,\quad 0 \le r < b.

Falls $r=0$ , dann ist $\operatorname{ggT}(a,b)=b$ .
Falls $r\neq 0$ , setze $a:=b$ , $b:=r$ und gehe zu Schritt 1 zurück.

Proof

Seien $a,b\in\mathbb{Z}$ und oEdA $a>b$ . Dann haben wir

\begin{align*} a &= q_1\cdot b + r_1\\ b &= q_2\cdot r_1 + r_2\\ r_1 &= q_3\cdot r_2 + r_3\\ &\vdots\\ r_{n-2} &= q_n\cdot r_{n-1} + r_n\\ r_{n-1} &= q_{n+1}\cdot r_n + 0\\ \end{align*}

Wir zeigen zuerst, dass sich in einer "Schleife" der ggT nicht ändert.

Wir setzen $t_1:=\operatorname{ggT}(a,b)$ . Sicher

t_1\mid a\text{ und } t_1\mid b,

d.h. $\exist k,l\in\mathbb{Z}$ mit $t_1k=a$ und $t_1l=b$ . Betrachte

a-q_1b=t_1k-q_1t_1l=t_1\underbrace{(k-q_1l)}_{\in\mathbb{Z}},

d.h. $t_1\mid (a-q_1b)$ . Also ist

\operatorname{ggT}(a,b)\leq\operatorname{ggT}(b,r_1)

Sei umgekehrt $t_2:=\operatorname{ggT}(b,a-q_1b)$ . Sicher

t_2\mid b\text{ und } t_2\mid (a-q_1b),

d.h. $\exist s,u\in\mathbb{Z}$ mit $t_2s=b$ und $t_2u=a-q_1b$ . Daraus folgt

a=t_2u+q_1b=t_2u+q_1t_2s=t_2\underbrace{(u+q_1s)}_{\in\mathbb{Z}},

d.h. $t_2\mid a$ . Also ist

\operatorname{ggT}(b,r_1)\leq\operatorname{ggT}(a,b),

insgesamt also

\operatorname{ggT}(b,r_1) = \operatorname{ggT}(a,b).

Im letzten Schritt des Algorithmus ist $\operatorname{ggT}(r_n,0)$ und wegen oben

\operatorname{ggT}(r_n,0)=\operatorname{ggT}(r_{n-1},r_n)=\dots=\operatorname{ggT}(a,b).

Da $\operatorname{ggT}(r_n,0)=r_n$ folgt die Behauptung.

Note 3

Pseudocode in Python kann so aussehen:

def euklid(a, b):
    while b != 0:
        r = a % b
        a, b = b, r
    return a

Example 1

Finde $\operatorname{ggT}(252,198)$ .

Solution

\begin{align*} 252 &= 1\cdot 198 + 54\\ 198 &= 3\cdot 54 + 36\\ 54 &= 1\cdot 36 + 18\\ 36 &= 2\cdot 18 + 0 \end{align*}

Also ist $\operatorname{ggT}(252,198)=18$ .

Exercise 3: \operatorname{ggT} mit Euklid'schem Algorithmus

Bestimme den grössten gemeinsamen Teiler von $544$ und $119$ mit dem Euklidischen Algorithmus.

Solution

Wir führen die Divisionen durch:

\begin{align*} 544 &= 4 \cdot 119 + 68 \\ 119 &= 1 \cdot 68 + 51 \\ 68 &= 1 \cdot 51 + 17 \\ 51 &= 3 \cdot 17 + 0 \end{align*}

Damit ist $\operatorname{ggT}(544,119)=17$ .

Exercise 4: ggT mit Euklid

Bestimme den grössten gemeinsamen Teiler (ggT) der Zahlen $153'900$ und $180'600$ mit dem Euklidischen Algorithmus.

Solution

Wir führen den Algorithmus aus:

\begin{align*} 180'600 &= 153'900 \cdot 1 + 26'700 \\ 153'900 &= 26'700 \cdot 5 + 20'400 \\ 26'700 &= 20'400 \cdot 1 + 6'300 \\ 20'400 &= 6'300 \cdot 3 + 1'500 \\ 6'300 &= 1'500 \cdot 4 + 300 \\ 1'500 &= 300 \cdot 5 + 0 \end{align*}

Der letzte von null verschiedene Rest ist $300$ . Also gilt:

\operatorname{ggT}(153'900,180'600) = 300

Zwischen dem ggT und dem kgV besteht der folgende Zusammenhang.

Theorem 2

a\cdot b=\text{ggT}(a,b)\cdot\text{kgV}(a,b)

Proof

Für das kgV nimmt man jeweils die maximal vorkommende Anzahl der Primfaktoren aus beiden Zahlen, für den ggT jeweils die minimale Anzahl der gemeinsamen Primfaktoren. Kommt also ein Primfaktor nur in einer der Zahlen vor, so wird er wegen des kgVs verwendet und taucht im ggT nicht auf. Kommt ein Faktor in beiden Zerlegungen vor, so wird er in seiner maximalen Anzahl wegen des kgVs genommen und wegen seiner minimalen Anzahl für den ggT. Also werden insgesamt alle Faktoren genau einmal im Produkt vorkommen.

Exercise 5: ggT und kgV mit Euklid

Bestimme den ggT und das kgV der Zahlen $5544$ und $4410$ mit dem euklidschen Algorithmus und dem letzten Satz.

Solution

\begin{align*} 5544 &= 4410\cdot1+1134\\ 4410 &= 1134\cdot3+1008\\ 1134 &= 1008\cdot1+126\\ 1008 &= 126\cdot8+0 \end{align*}

Der ggT ist also $126$ . Damit ist das kgV $\frac{5544\cdot4410}{126}=194'040$ .

Lemma von Bézout

Das Lemma von Bézout liefert eine wichtige Verbindung zwischem dem grössten gemeinsamen Teiler zweier Zahlen und seiner Darstellung als Linearkombination der beiden.

Example 2

Betrachten wir beispielsweise $a=15$ und $b=21$ , so sehen wir folgende Linearkombinationen $ax+by$ :

$x$	$y$	$ax+by$
$1$	$0$	$15$
$0$	$1$	$21$
$1$	$1$	$36$
$-1$	$0$	$-15$
$0$	$-1$	$-21$
$1$	$-1$	$-6$
$-1$	$1$	$6$
$-3$	$2$	$-3$
$3$	$-2$	$3$
$2$	$-1$	$9$

Wir beobachten, dass die Linearkombinationen alle Vielfache von $3$ sind.

Theorem 3: Lemma von Bézout

Seien $a, b \in \mathbb{Z}$ und nicht beide null. Dann existieren ganze Zahlen $x, y \in \mathbb{Z}$ , sodass

\operatorname{ggT}(a, b) = ax + by.

Proof

Betrachte die Menge

S = \{ ax + by \mid x, y \in \mathbb{Z},\ ax + by > 0 \}.

Da $a$ und $b$ nicht beide $0$ sind, ist $S \neq \emptyset$ . Nach dem Wohlordnungsprinzip besitzt $S$ ein kleinstes Element. Bezeichne dieses mit

d = ax_0 + by_0.

Wir zeigen $d \mid a$ und $d \mid b$ :
Zuerst $d \mid a$ . Dazu führen wir die Division mit Rest aus:

a = qd + r,\quad 0 \le r < d.

Dann gilt für den Rest

r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0).

Also ist $r \in S\cup\{0\}$ . Wäre $r > 0$ , so hätten wir wegen $r<d$ ein kleineres Element als $d$ in $S$ , Widerspruch. Also muss $r = 0$ , d.h. $d \mid a$ .
Analog folgt $d \mid b$ .

Bleibt noch zu zeigen, dass $d$ der grösste Teiler ist:
Sei $d'$ ein weiterer gemeinsamer Teiler von $a$ und $b$ . Dann teilt $d'$ auch jede Linearkombination $ax + by$ , insbesondere $ax_0 + by_0 = d$ . Also $d' \mid d$ . Das heisst $d$ ist der grösste gemeinsame Teiler und wir sind fertig.

Im obigen Beweis wurde das Wohlordnungsprinzip verwendet, das wir der Vollständigkeit halber hier notieren.

Theorem 4: Wohlordnungsprinzip

Jede nichtleere Teilmenge der natürlichen Zahlen $\mathbb{N}$ besitzt ein kleinstes Element.
Das heisst: Ist $M \subseteq \mathbb{N}$ mit $M \neq \emptyset$ , so existiert ein $m_0 \in M$ , sodass $m\ge m_0$ für alle $m \in M$ gilt.

Proof

BWoC: Sei $M \subseteq \mathbb{N}$ und $M \neq \emptyset$ . Angenommen, $M$ besitze kein kleinstes Element.
Dann gilt für jede Zahl $n \in \mathbb{N}$ : Es gibt ein $m \in M$ mit $m < n$ . Aber für die kleinste natürliche Zahl $n = 1$ müsste ein $m < 1$ existieren, was wegen $m\in\mathbb{N}$ unmöglich ist. Dies widerspricht der Annahme, dass $M$ kein kleinstes Element besitzt.

Hilfreich ist manchmal folgender Satz, dessen Beweisvariante den Satz von Bézout verwendet.

Theorem 5: Lemma von Euklid

Sei $p$ eine Primzahl und $a,b\in\mathbb{Z}$ . Falls $p\mid ab$ , dann gilt

p\mid a \quad\text{oder}\quad p\mid b.

Proof

Ich zeige dies meist mit einer Gegenannahme, möchte hier aber eine direkte Variante präsentieren:

Nehmen wir an, $p\mid ab$ .

Falls $p\mid a$ , ist die Behauptung sofort erfüllt.
Falls nicht, gilt $\operatorname{ggT}(p,a)=1$ , da $p$ prim ist und $p\nmid a$ .
Nach dem Satz von Bézout existieren $u,v\in\mathbb{Z}$ mit $up+va=1.$ Multiplizieren wir mit $b$ : $ubp+vab=b.$ Da $p\mid ubp$ und $p\mid vab$ (weil $p\mid ab$ ), folgt $p\mid b$ .