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=42,b=123$

Schritt	$a$	$b$	Ausgabe
1	42	123
2
3
4
5		81
3
4
5		39
3
4	3
3
4
5		36
3
4
5		33
3
4
5		30
3
4
5		27
3
4
5		24
3
4
5		21
3
4
5		18
3
4
5		15
3
4
5		12
3
4
5		9
3
4
5		6
3
4
5		3
3
4
5		0
3			3

Der ggT von 42 und 123 ist also 3.