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

A B Q R S T U V Berechnung
120 23 1 0 0 1 Startwerte
120 23 5 5 Q = A / B = 120 / 23 = 5
R = A % B = 120 % 23 = 5
120 23 5 5 0 1 S = Ualt = 0
T = Valt = 1
120 23 5 5 0 1 1 -5 U = Salt - (Q · Ualt) = 1 - (5 · 0) = 1
V = Talt - (Q · Valt) = 0 - (5 · 1) = -5
120 23 5 5 0 1 1 -5 Q = A / B = 120 / 23 = 5
R = A % B = 120 % 23 = 5
S = Ualt = 0
T = Valt = 1
U = Salt - (Q · Ualt) = 1 - (5 · 0) = 1
V = Talt - (Q · Valt) = 0 - (5 · 1) = -5
23 5 A = Balt = 23
B = R = 5
23 5 4 3 Q = A / B = 23 / 5 = 4
R = A % B = 23 % 5 = 3
23 5 4 3 1 -5 S = Ualt = 1
T = Valt = -5
23 5 4 3 1 -5 -4 21 U = Salt - (Q · Ualt) = 0 - (4 · 1) = -4
V = Talt - (Q · Valt) = 1 - (4 · -5) = 21
23 5 4 3 1 -5 -4 21 Q = A / B = 23 / 5 = 4
R = A % B = 23 % 5 = 3
S = Ualt = 1
T = Valt = -5
U = Salt - (Q · Ualt) = 0 - (4 · 1) = -4
V = Talt - (Q · Valt) = 1 - (4 · -5) = 21
5 3 A = Balt = 5
B = R = 3
5 3 1 2 Q = A / B = 5 / 3 = 1
R = A % B = 5 % 3 = 2
5 3 1 2 -4 21 S = Ualt = -4
T = Valt = 21
5 3 1 2 -4 21 5 -26 U = Salt - (Q · Ualt) = 1 - (1 · -4) = 5
V = Talt - (Q · Valt) = -5 - (1 · 21) = -26
5 3 1 2 -4 21 5 -26 Q = A / B = 5 / 3 = 1
R = A % B = 5 % 3 = 2
S = Ualt = -4
T = Valt = 21
U = Salt - (Q · Ualt) = 1 - (1 · -4) = 5
V = Talt - (Q · Valt) = -5 - (1 · 21) = -26
3 2 A = Balt = 3
B = R = 2
3 2 1 1 Q = A / B = 3 / 2 = 1
R = A % B = 3 % 2 = 1
3 2 1 1 5 -26 S = Ualt = 5
T = Valt = -26
3 2 1 1 5 -26 -9 47 U = Salt - (Q · Ualt) = -4 - (1 · 5) = -9
V = Talt - (Q · Valt) = 21 - (1 · -26) = 47
3 2 1 1 5 -26 -9 47 Q = A / B = 3 / 2 = 1
R = A % B = 3 % 2 = 1
S = Ualt = 5
T = Valt = -26
U = Salt - (Q · Ualt) = -4 - (1 · 5) = -9
V = Talt - (Q · Valt) = 21 - (1 · -26) = 47
2 1 A = Balt = 2
B = R = 1
2 1 2 0 Q = A / B = 2 / 1 = 2
R = A % B = 2 % 1 = 0
2 1 2 0 -9 47 S = Ualt = -9
T = Valt = 47
1 -9 47 Endergebnis

Ergebnis:
ggT(120, 23) = 1
-9 · 120 + 47 · 23 = ggT(120, 23) = 1

Die Zahl -9 ist das multiplikative inverse Element von 120 im Ring Z23, also 120 · -9 = -1080 = 1 mod 23.
-9 ist gleich 14 mod 23, daher gilt natürlich auch: 14 ist das multiplikative inverse Element von 120 im Ring Z23, also 120 · 14 = 1680 = 1 mod 23.

Die Zahl 47 ist das multiplikative inverse Element von 23 im Ring Z120, also 23 · 47 = 1081 = 1 mod 120.