Jak obliczyć odwrotność liczby a modulo n gdy NWD(a, n) = 1?

Odwrotnością liczby a modulo n nazywamy taką liczbę całkowitą x, że iloczyn ax daje resztę 1 z dzielenia przez n:

ax = ny + 1.

Zatem aby wyznaczyć x trzeba rozwiązać równanie diofantyczne

ax - ny = 1.

Można to zrobić sposobem opisanym powyżej