Największy wspólny dzielnik dwóch liczb może być przedstawiony w postaci kombinacji liniowej tych liczb ze współczynnikami całkowitymi:
NWD(a, b) = x*a + y*b
przy czym zarówno NWD jak i liczby x oraz y można znaleźć w czasie O(ln²(a)).
I właśnie do znalezienia takiej kombinacji liniowej służyć może przedstawiony tutaj rozszerzony algorytm Euklidesa.

Ponadto algorytm ten może być użyty do znalezienia liczby odwrotnej do b mod a
Liczba odwrotna do liczby b mod a jest to liczba y spełniającą równanie:
b * y mod a = 1
co zapisuje się jako
b * y ≡ 1 (mod a)
przy czym liczbę odwrotną b mod a można znaleźć również w czasie O(ln²(a)). Liczba ta jednak istnieje, jeżeli NWD(a, b)=1.

Algorytm przebiega następująco (zakładamy, że a>b):

Przypiszmy początkowe wartości:
q = Floor(a/b) - cześć całkowita z dzielenia a/b
r = a - q*b - reszta z dzielenia a/b
nwd = b - początkowa wartość wyniku, gdyby już teraz reszta wynosiła 0

Zainicjuj pomocnicze zmienne do obliczenia wartości dla kombinacji liniowej i odwrotności b mod a
x_i-2 = 1
x_i-1 = 0
x_i = 1
y_i-2 = 0
y_i-1 = 1
y_i = (q-1) - początkowa wartość wyniku, gdyby już teraz reszta wynosiła 0.

Dopóki reszta r jest różna od zera wykonuj następujące kroki (i - oznacza numer iteracji, zainicjowane początkowo wartosci x_i oraz y_i zostają nadpisane podczas pierwszej iteracji):
  a = b
  b = r
  x_i = x_i-2 - q*x_i-1
  y_i = y_i-2 - q*y_i-1
  i = i + 1
  nwd = r
  q = Floor(a/b); - cześć całkowita z dzielenia a/b
  r = a - q*b - reszta z dzielenia a/b

Zwróć uwagę, że w trakcie obliczeń potrzebne są tylko 3 wartości x oraz y, z bieżącej iteracji, poprzedniej i przedpoprzedniej. Nie trzeba zatem tworzyć tablicy a wystarczą jedynie 3 zmienne.
Jeżeli reszta wynosi 0 to, wówczas wynik przechowywany jest w zmiennej nwd
Współczynniki kombinacji liniowej przechowywane są w zmiennych x_i oraz y_i, oryginalne wartości a oraz b zostały zniszczone podczas prowadzenia obliczeń więc należy je zapamiętać przed przeprowadzeniem obliczeń.
Ponadto jeżeli NWD(a, b) = 1, to liczba odwrotna do liczby b mod a jest przechowywana w zmiennej y_i.

Przykłady

a = 6
b = 3

i	a	b	q	r	nwd	xi	xi-1	xi-2	yi	yi-1	yi-2
1	6	3	2	0	3	1	0	1	-1	1	0

NWD(6, 3) = 3 = 1 * 6 + -1 * 3

a = 84
b = 15

i	a	b	q	r	nwd	xi	xi-1	xi-2	yi	yi-1	yi-2
1	84	15	5	9	15	1	0	1	-4	1	0
1	15	9	1	6	9	1	0	1	-5	1	0
2	9	6	1	3	6	-1	1	0	6	-5	1
3	6	3	2	0	3	2	-1	1	-11	6	-5

NWD(84, 15) = 3 = 2 * 84 + -11 * 15

a = 26
b = 15

i	a	b	q	r	nwd	xi	xi-1	xi-2	yi	yi-1	yi-2
1	26	15	1	11	15	1	0	1	0	1	0
1	15	11	1	4	11	1	0	1	-1	1	0
2	11	4	2	3	4	-1	1	0	2	-1	1
3	4	3	1	1	3	3	-1	1	-5	2	-1
4	3	1	3	0	1	-4	3	-1	7	-5	2

NWD(26, 15) = 1 = -4 * 26 + 7 * 15
15 * 7 mod 26 = 1