Der erweiterte euklidische Algorithmus ist ein Algorithmus, der den größten gemeinsamen Teiler von zwei Zahlen bestimmt (den ggT) und zusätzlich die sogenannten Bézout-Koeffizienten für diese zwei Zahlen sehr effizient berechnen kann. Die Bézout-Koeffizienten "s" und "t" der Zahlen "n" und "m" erfüllen folgende Beziehung:

s * n + t * m = ggT(n, m)

Falls der ggT von "n" und "m" 1 ist, haben die Bézout-Koeffizienten eine besondere Bedeutung: in den Beiden Ringen Z_n und Z_m sind jeweils "s" und "t" die multiplikativen inversen Elemente von m und n. Es gilt also:

Im Z_n: m^-1 = t, also m*t = 1 mod n
Im Z_m: n^-1 = s, also n*s = 1 mod m

Zahl 1:
Zahl 2:
	Detailliert
	Schritt für Schritt