Euklidischer Algorithmus

Der Euklidische Algorithmus ist ein Algorithmus zur Berechnung des größten gemeinsamen Teilers (ggT) zweier Zahlen. Der Algorithmus wurde im 3. Jahrhundert v.u.Z. von dem griechischen Mathematiker Euklid erfunden und funktioniert so:

1. Gegeben sind zwei Zahlen $a$ und $b$, deren ggT berechnet werden soll.
2. Falls $a=0$, gib $b$ aus; nach der Ausgabe ist der Ablauf beendet.
3. Falls $b=0$, gib $a$ aus; nach der Ausgabe ist der Ablauf beendet.
4. Falls $a>b$, setze $a:=a-b$.
5. Sonst setze $b:=b-a$
6. Springe zurück zu Schritt 3

Beispiel

Die folgende Trace-Tabelle illustriert den Algorithmus für die Eingabe $a=666,b=123$

Schritt	$a$	$b$	Ausgabe
1	666	123
2
3
4	543
3
4	420
3
4	297
3
4	174
3
4	51
3
5		72
3
5		21
3
4	30
3
4	9
3
5		12
3
5		3
3
4	6
3
4	3
3
5		0
3			3

Der ggT von 666 und 123 ist also 3.