Let $x$ — value, $M$ — mod, $y$ — $x^{-1}\,(mod\,M)$.↵
$$xy = kM+1$$↵
where $k$ is integer↵
$$yx - kM = 1$$↵
You can see this is just Diophantine equation with coefficients $a=x$, $b=M$, $c=1$.↵
↵
So we can use extended euclidean algorithm.↵
↵
↵
~~~~~↵
def gcd_ext(a, b):↵
if b == 0:↵
return a, 1, 0↵
d, x, y = gcd_ext(b, a % b)↵
x, y = y, x - (a // b) * y↵
return d, x, y↵
↵
↵
x = 7↵
mod = int(1e9)↵
d, inv, k = gcd_ext(x, mod)↵
# d is gcd(x, mod), if d isn't 1, then inverse is non exist↵
print(inv % mod, k)↵
~~~~~↵
↵
$$xy = kM+1$$↵
where $k$ is integer↵
$$yx - kM = 1$$↵
You can see this is just Diophantine equation with coefficients $a=x$, $b=M$, $c=1$.↵
↵
So we can use extended euclidean algorithm.↵
↵
↵
~~~~~↵
def gcd_ext(a, b):↵
if b == 0:↵
return a, 1, 0↵
d, x, y = gcd_ext(b, a % b)↵
x, y = y, x - (a // b) * y↵
return d, x, y↵
↵
↵
x = 7↵
mod = int(1e9)↵
d, inv, k = gcd_ext(x, mod)↵
# d is gcd(x, mod), if d isn't 1, then inverse is non exist↵
print(inv % mod, k)↵
~~~~~↵
↵
