TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 52
Man bestimme den ggT(2107,9849) mit Hilfe des Euklidischen Algorithmus.
Lösung von D4ni31[Bearbeiten | Quelltext bearbeiten]
9849 2107 4 1421
2107 1421 1 686
1421 686 2 49
686 49 14 0
ggt(9849,2107)=49
Lösung von Fischkopf[Bearbeiten | Quelltext bearbeiten]
Die erste Lösung stimmt jedoch im Allgemeinen, jedoch ist sie sehr ungenau beschrieben. Ich schreibs hier nochmal etwas genauer auf, falls es doch jemand gibt der das ganze noch nicht so genau verstanden hat (dem hilft die obere Lösung nämlich nur sehr wenig ;))
Ich mach es meistens so, ich schreibe zuerst die Angabe ungefähr so auf:
9849 = * 2107 +
Die größere Zahl zuerst und dann dividieren (9849/2107 = 4 REST 1421), das wir dann so eingefügt:
9849 = 4 * 2107 + 1421
In der nächsten Zeile verschieben wir dann 2 Zahlen nach Links und wiederholen den Schritt von eben immer wieder:
2107 = 1 * 1421 + 686 (2107/1421 = 1 REST 686)
1421 = 2 * 686 + 49 (1421/686 = 2 REST 49)
686 = 14 * 49 + 0 (686/49 = 14 REST 0)
Sobald wir bei Rest 0 Angekommen sind, nehmen wir den letzten erhaltenen Rest (49) und haben so unseren ggT.
ggT(2107,9849) = 49