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.
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:
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.