TU Wien:Mathematik 1 UE (diverse)/Übungen SS10/Beispiel 8

Man bestimme den $ggT(2010,6318)$ mit Hilfe des Euklidischen Algorithmus.

Lösung

${\begin{aligned}6318&=2010*3+288\\2010&=288*6+282\\288&=282*1+6\\282&=6*47+0\\ggT(2010,6318)&=6\end{aligned}}$

Man fängt immer damit an das Vielfache der kleineren Zahl von der größeren zu suchen und addiert den Rest, schreitet dann mit der nächstgrößten Zahl voran und schaut wie oft der Rest vom letzten mal rein passt; addiert wieder den Rest usw. bis kein Rest mehr bleibt - der ggT ist also 6.

Lady Joker