Euklidischer Algorithmus

Studium

\operatorname{ggT}(a, b) = \operatorname{ggT}(b,\ a \bmod b), \qquad \operatorname{ggT}(a, 0) = a

Voraussetzung: $a, b \in \mathbb{N}_0;$ $b \geq 1$ $in der ersten,$ $a \geq 1$ $in der zweiten Gleichung$

$a, b$: natürliche Zahlen, deren größter gemeinsamer Teiler gesucht ist
$\operatorname{ggT}(a, b)$: größter gemeinsamer Teiler von a und b
$a \bmod b$: Rest bei der Division von a durch b, eine Zahl zwischen 0 und b−1

Der ggT zweier Zahlen ändert sich nicht, wenn man die größere durch ihren Rest bei Division durch die kleinere ersetzt.

Erklärung

Der Euklidische Algorithmus bestimmt den größten gemeinsamen Teiler zweier Zahlen, ohne sie in Primfaktoren zu zerlegen. Er beruht auf der Regel

\operatorname{ggT}(a, b) = \operatorname{ggT}(b,\ a \bmod b)

Grund: Ist $a = q \cdot b + r$ mit $0 \leq r < b$ , dann teilt jeder gemeinsame Teiler von $a$ und $b$ auch $r = a - q \cdot b$ , und jeder gemeinsame Teiler von $b$ und $r$ teilt auch $a$ . Beide Paare haben also dieselben gemeinsamen Teiler.

Ablauf: Man teilt mit Rest, ersetzt $(a, b)$ durch $(b, r)$ und wiederholt das. Die Reste werden echt kleiner, also erreicht man nach endlich vielen Schritten den Rest $0$ . Der letzte von null verschiedene Rest ist der ggT.

Der Algorithmus ist sehr schnell: Die Zahl der Schritte wächst nur logarithmisch mit der Größe der Zahlen (Satz von Lamé). Am langsamsten ist er bei aufeinanderfolgenden Fibonacci-Zahlen.

Beispiele

$\operatorname{ggT}(1071, 462)$ :

\begin{aligned} 1071 &= 2 \cdot 462 + 147 \\ 462 &= 3 \cdot 147 + 21 \\ 147 &= 7 \cdot 21 + 0 \end{aligned}

Der letzte Rest ungleich null ist $21$ , also $\operatorname{ggT}(1071, 462) = 21$ .

$\operatorname{ggT}(252, 105)$ :

\begin{aligned} 252 &= 2 \cdot 105 + 42 \\ 105 &= 2 \cdot 42 + 21 \\ 42 &= 2 \cdot 21 + 0 \end{aligned}

Ergebnis: $\operatorname{ggT}(252, 105) = 21$ .

Typische Fehler

Den Rest $0$ oder den letzten Quotienten als Ergebnis nehmen. Der ggT ist der letzte Rest vor der $0$ , im ersten Beispiel $21$ , nicht der Quotient $7$ .
Quotient und Rest verwechseln. Weiter geht es immer mit dem Paar (alter Divisor, Rest), nicht mit dem Quotienten.
Nach dem ersten Schritt aufhören. Bei $\operatorname{ggT}(34, 21)$ braucht man sieben Divisionen, bis der Rest $0$ ist; das Ergebnis ist $1$ , die Zahlen sind teilerfremd.
Mit $b = 0$ teilen wollen. Für $b = 0$ gilt direkt $\operatorname{ggT}(a, 0) = a$ .

Euklidischer Algorithmus