6161619795

Dla elementu odwrotnego do a wprowadza się oznaczenie a -I .

Jeżeli istnieje element odwrotny, to jest on unikalny (tzn.określony jednoznacznie), a ponadto:

a a'! (mod n) = 1

Jeżeli b e $ _n jest odwracalne, to wynik operacji dzielenia a przez b modulo n jest określony przez iloczyn ab -1 (mod n).

a e %_n jest odwracalne <±>gcd (a, n) = 1

Rozszerzony algorytm Euklidesa umożliwia obliczanie elementu odwrotnego w zbiorze ^ _n.

W tym celu wystarczy zauważyć, że jeśli a i b są względnie pierwsze, to :

d = gcd (a, b) = ax + by = 1    (*)

d, x i y są zwracane przez funkcję Ext_Euclid wywołaną z parametrami a i b.

Równanie (*) jest równoważne równaniu:

(ax + by) = 1 (mod b) (**) a ponieważ y jest liczbą całkowitą, więc :

(by) =0 (modb)

a stąd:    ax = / (mod b)

czyli:    x =a (mod b)