Euklidischer Algorithmus (Z)/ggT/71894 und 45327/Aufgabe mit Lösung

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.