Euklidischer Algorithmus

Der euklidische Algorithmus dient der Bestimmung des größten gemeinsamen Teilers (siehe größter gemeinsamer Teiler) zweier Zahlen. Der größte gemeinsame Teiler lässt sich durch die Folge

x[j] = x[j - 2] mod x[j - 1] für x[j - 1] > 0 und j >= 1

bestimmen. Der ggT ist die letzte, von Null verschiedene Zahl x[n] der Folge.

Mit dem euklidischen Algorithmus lassen sich auch zwei Zahlen p[n+1] und q[n+1] bestimmen, so dass

ggT(x[0], x[1]) = x[n] = p[n + 1] x[0] + q[n + 1] x[1]

gilt. Dafür definiert man rekursiv für 0 <= i <= n:

p[0] = 0,
q[0] = 1,
p[i + 1] = q[i],
q[i + 1] = p[i] - x[n - i] * q[i].