Lösung für Aufgabe 5.3.58
Bestimmen Sie den größten gemeinsamen Teiler der Zahlen aus Aufgabe 5.3.52 mit Hilfe des euklidischen Algorithmus.\begin{eqnarray*} 3471873 &\ident& 8187333 \mod 4715460\\ 1243587 &\ident& 4715460 \mod 3471873\\ 984699 &\ident& 3471873 \mod 1243587\\ 258888 &\ident& 1243587 \mod 984699\\ 208035 &\ident& 984699 \mod 258888\\ 50853 &\ident& 258888 \mod 208035\\ 4623 &\ident& 208035 \mod 50853\\ 0 &\ident& 50853 \mod 4623 \end{eqnarray*} Daher ist $4623$ der gesuchte ggT.