Euklidischer Algorithmus/Z/Einführung/Textabschnitt

Es seien ${}a,b$ ganze Zahlen, ${}b\neq 0$. Dann kann man die Division mit Rest durchführen und erhält ${}a=qb+r$ mit ${}0\leq r<\vert {b}\vert$. Danach kann man (bei ${}r\neq 0$) die Division mit Rest von ${}b$ durch ${}r$ durchführen, d.h. ${}b$ nimmt die Rolle von ${}a$ und ${}r$ die Rolle von ${}b$ ein und erhält einen neuen Rest. Dies kann man fortsetzen, und da dabei die Reste immer kleiner werden bricht das Verfahren irgendwann ab.

Euklid (4. Jahrhundert v. C.)

Definition

Es seien zwei ganze Zahlen ${}a,b$ (mit ${}b\neq 0$) gegeben. Dann nennt man die durch die Anfangsbedingungen ${}r_{0}=a$ und ${}r_{1}=b$ und die mittels der Division mit Rest

${}r_{i}=q_{i}r_{i+1}+r_{i+2}\,$

rekursiv bestimmte Folge ${}r_{i}$ die Folge der euklidischen Reste.

Satz

Es seien ganze Zahlen ${}r_{0}=a$ und ${}r_{1}=b\neq 0$ gegeben.

Dann besitzt die Folge ${}r_{i}$, ${}i=0,1,2,\ldots$, ${},$ der euklidischen Reste folgende Eigenschaften.

1. Es ist ${}r_{i+2}=0$ oder ${}r_{i+2}<r_{i+1}$.
2. Es gibt ein (minimales) ${}k\geq 2$ mit ${}r_{k}=0$.
3. Es ist

   ${}\operatorname {ggT} (r_{i-1},r_{i})=\operatorname {ggT} (r_{i},r_{i+1})\,$

   für alle ${}i=1,\ldots ,k$

4. Sei ${}k\geq 2$ der erste Index derart, dass ${}r_{k}=0$ ist. Dann ist

   ${}\operatorname {ggT} (a,b)=r_{k-1}\,.$

Beweis

1. Dies folgt unmittelbar aus der Definition der Division mit Rest.
2. Solange ${}r_{i}\neq 0$ ist, wird die Folge der natürlichen Zahlen ${}r_{i}$ immer kleiner, so dass irgendwann der Fall ${}r_{i}=0$ eintreten muss.
3. Wenn ${}t$ ein gemeinsamer Teiler von ${}r_{i}$ und von ${}r_{i+1}$ ist, so zeigt die Beziehung

   ${}r_{i-1}=q_{i-1}r_{i}+r_{i+1}\,,$

   dass ${}t$ auch ein Teiler von ${}r_{i-1}$ und damit ein gemeinsamer Teiler von ${}r_{i-1}$ und von ${}r_{i}$ ist. Die Umkehrung folgt genauso.

4. Dies folgt aus (3) mit der Gleichungskette

   ${}\operatorname {ggT} (a,b)=\operatorname {ggT} (b,r_{2})=\operatorname {ggT} (r_{2},r_{3})=\ldots =\operatorname {ggT} (r_{k-2},r_{k-1})=\operatorname {ggT} (r_{k-1},r_{k})=\operatorname {ggT} (r_{k-1},0)=r_{k-1}\,.$

$\Box$

Beispiel

Aufgabe

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}71894$ und ${}45327$.

Lösung

Der Euklidische Algorithmus liefert:

$71894=1\cdot 45327+26567$

$45327=1\cdot 26567+18760$

$26567=1\cdot 18760+7807$

$18760=2\cdot 7807+3146$

$7807=2\cdot 3146+1515$

$3146=2\cdot 1515+116$

$1515=13\cdot 116+7$

$116=16\cdot 7+4$

$7=1\cdot 4+3$

$4=1\cdot 3+1.$

Die Zahlen ${}71894$ und ${}45327$ sind also teilerfremd.

Bei kleinen Zahlen sieht man häufig relativ schnell direkt, was ihr größter gemeinsamer Teiler ist, da man die Primfaktorzerlegung kennt bzw. mögliche gemeinsame Teiler schnell übersehen kann. Bei zwei größeren Zahlen müssten aber viel zu viele Probedivisionen durchgeführt werden! Der euklidische Algorithmus ist also zur Bestimmung des größten gemeinsamen Teilers ein sehr effektives Verfahren!