Auf dieser Seite wird der Euklid'sche Algorithmus behandelt, der bereits um 300 v.Chr vom griechischen Mathematiker Euklid entwickelt wurde.

Mit Hilfe des Euklid'schen Algorithmus wird der größte gemeinsame Teiler (ggT) zweier Zahlen berechnet. Die Berechnung erfordert - ansonsten wäre der Algorithmus nutzlos - deutlich weniger Schritte als ein Durchprobieren aller Zahlen bis hin zur kleineren der beiden zu untersuchenden Zahlen.

Man nehme die beiden Zahlen 217 und 63. Um den größten gemeinsamen Teiler zu finden könnte man nun alle Zahlen von 1 bis hin zu 63 durchprobieren. Eine bessere Lösung ist der Euklid'sche Algorithmus.

Zunächst wird die Größere der beiden Zahlen - hier 217 - durch die Kleinere - im Beispiel 63 - geteilt.

   217 = 3 * 63 + 28

Bei der Division bleibt ein Rest von 28, welcher hier für uns eine wichtige Bedeutung hat. Den nun haben wir unser Problem dahingehend vereinfacht, dass wir nur mehr den größten gemeinsamen Teiler von 63 und 28 finden müssen.

Dieses Verfahren kann nun auch auf die Zahlen 63 und 28 angewandt werden. Wiederholt man das Verfahren so lange, bis bei der Division ein Rest von 0 bleibt (die maximale Anzahl an Schritten entspricht dem größeren der beiden Startwerte), dann hat man den ggT im Rest des vorherigen Durchlaufes gefunden.

Um das Beispiel zu Ende zu führen:

   217 = 3 * 63 + 28
   63 = 2 * 28 + 7
   28 = 4 * 7 + 0

Der ggT von 217 und 63 ist somit 7.

Wenn x der ggT von 217 und 63 ist, dann ist

   217 = a * X und 63 = b * X

Daraus folgt, dass

   28 = 217 - 3 * 63 = a * X - 3 * b * X = X * (a - 3 * b)

und damit ist 28 ein Vielfaches von X.

unsigned int ggT (unsigned int a, unsigned int b)
{
	unsigned int r0, r1;
	unsigned int rmod;
	if (a < b) { rmod = a; r1 = b; } else { rmod = b; r1 = a; }
	do {
		r0 = r1;
		r1 = rmod;
		rmod = r0 % r1;
	} while (rmod > 0);
	return r1;
}