Rozszerzony algorytm Euklidesa sluzy do wyznaczania x, takiego, ze:

a * x mod n = 1,

gdzie a jest liczba; calkowita; z przedzialu [0, n-1]. W skrocie zapisuje sie to tak:

x = inv(a, n)

Przedstawmy ten algorytm w postaci uproszczonego pseudokodu zblizonego do jezyka programowania Pascal.

begin

aaag0 : = na;aaa g1 : = aa;

aaau0 : = 1a; aaav0 : = 0a;

aaau1 : = 0 ; aaav1 : = 1 ;

aaai : = 1 ;

aaawhile gi <> 0 do "gi : = ui * n + vi * a"

aaaaaaaaaaaabegin

aaaaaaaaaaaaaaaaaay : = gi-1 div gi ;

aaaaaaaaaaaaaaaaaagi+1 : = gi-1 - y * gi ;

aaaaaaaaaaaaaaaaaaui+1 : = ui-1 - y * ui ;

aaaaaaaaaaaaaaaaaavi+1 : = vi-1 - y * vi ;

aaaaaaaaaaaaaaaaaai : = i + 1

aaaaaaaaaaaaend ;

aaax : = vi-1 ;

aaaif x >= 0 then

aaaaaaaaaaaaaaaainv : = x

aaaelse

aaaaaaaaaaaaaaaainv : = x + n

end