Suppose that gcd(n,m) = 1. To compute the inverse of n modulo m, run the extended Euclid algorithm, obtaining numbers x and y such that n*x + m*y = 1. Taking this equation mod m, we see that n*x = 1 (mod m). So x is the inverse of n modulo m.
Here is the algorithm.
Euclid(n,m)
if m = 0 then return (n,1,0)
else
(d',x',y') = Euclid(m, n mod m)
q = floor(n/m)
(d,x,y) = (d', y', x' - q*y')
return (d,x,y)
end if
test-for-prime(n,k) if n is even then return COMPOSITE end if for i = 1,2,...,k w = random(1,n-1) if witness(w,n) then return COMPOSITE end if end for return PRIMEThe witness function is as follows. It is mainly based on Fermat's Little Theorem, that x^(p-1) = 1 (mod p) whenever p is prime and x != 0 (mod p).
witness(w,n) let (b[k], b[k-1], ..., b[1], b[0]) be the binary representation of n-1, where b[0] is the least significant bit. d = 1 for i = k downto 0 do x = d d = (d*d) mod n if d = 1 and x != 1 and x != n-1 then return true end if if b[i] = 1 then d = (d*w) mod n end if end for if d = 1 then return false else return true endif