Euklidischer Algorithmus

Einleitung

Der Euklidische Algorithmus stellt ein Verfahren zum systematischen Bestimmen des GGT, des Größten Gemeinsamen Teilers, dar. Systematisch ist ein sehr schönes Wort. Der Computer ist ja eigentlich ziemlich blöd, aber wenn man ihm Schritt für Schritt erklärt, was er zu tun hat, dann findet sich kein Mensch auf dieser Welt, der die gleiche Aufgabe in dieser Präzision und Fehlerfreiheit durchführen könnte. Mit dem Euklidischen Algorithmus haben wir nun eine Möglichkeit gefunden, dem Computer die Bestimmung des GGT beizubringen.

Algorithmus

Das einfachste wird sein, wenn ich einfach ein Beispiel bringe, um nicht mit irgendwelchen wirren Formeln und Variablen um mich schmeissen zu müssen:

Versuchen wir einmal, den GGT( 19, 4 ) zu bestimmen:

19 = 4 * 4 + 3
 4 = 1 * 3 + 1    <<-- GGT( 19,4 ) = 1
 3 = 3 * 1 + 0

Eigentlich doch gar nicht so kompliziert. Durch die farblichen Markierungen ist hoffentlich das System klar geworden:

1. Die Zahl links vom Gleichheitszeichen wird auf der rechten Seite jeweils mit dem Ergebnis aus den Operatoren DIV und MOD dargestellt.
2. Im nächsten Schritt werden die Zahlen dann nach links verschoben.
3. Ist das Ergebnis des Rest = 0, so ist der GGT der Rest der Gleichung im Schritt zuvor.
4. Und schon vorbei

Vielleicht noch eine kleine Anmerkung, wenn man am Anfang die kleinere Zahl nach links schreibt, dann bringt das Verfahren nicht wirklich Sinn. Wer es nicht glaubt, der kann dieses gerne ausprobieren.