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:

latex:s \* n + t \* m = \textnormal{gcd}(n, m)

Hierbei steht "gcd" für greatest common divisor, also größter gemeinsamer Teiler. Falls der ggT von "n" und "m" 1 ist, haben die Bézout-Koeffizienten eine besondere Bedeutung: in den beiden Ringen Zn und Zm sind jeweils "s" und "t" die multiplikativen inversen Elemente von m und n. Es gilt also:

latex:m^{-1} = t \mod n \rightarrow m \* t = 1 \mod n
latex:n^{-1} = s \mod m \rightarrow n \* s = 1 \mod m