TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS12/Beispiel 39

Man bestimme den ggT(7469, 2464) mit Hilfe des Euklidischen Algorithmus.

Berechnung mittels Euklidischen Algorithmus.

$7469=2464\cdot 3+77$

$2464=77\cdot 32+0$

$\Rightarrow ggT(7469,2464)=77$

Der größte gemeinsame Teiler ist der letzte Rest der $\ne 0$ ist!