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