Solving a modular equation (Python)

Question

I have what seems to be an easy problem to solve in Python, but as I am new to python I am unaware on how to solve this.

All I am trying to solve is...

(x * e) mod k = 1 (where e and k are known values)

Is there any simple way of doing this?

Answer 1

Searching for x is basically looking for inverse element of e mod k which can be done by Extended Euclidean Algorithm which nicely implemented and used for modular inverse here:

# Iterative Algorithm (xgcd)
def iterative_egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q,r = b//a,b%a; m,n = x-u*q,y-v*q # use x//y for floor "floor division"
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

def modinv(a, m):
    g, x, y = iterative_egcd(a, m) 
    if g != 1:
        return None
    else:
        return x % m

_{Note: I don't own the code}

And usage:

>>> e = 3
>>> k = 7
>>> x = modinv(e,k)
>>> x
5
>>> e*x % k
1