A python code for calculate GCD and modular multiplicative inverse

modular-multiplicative-inverse.py

def inverseMod(a, m):
    for i in range(1,m):
        if ( m*i + 1) % a == 0:
            return ( m*i + 1) // a
    return None

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.
    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a


a = input("Input a number of \"a\": ")
b = input("Input a number of \"b\": ")


print("The Greatest Common Divisor of %s and %s is %s" % (a, b, gcd(a,b)))
print("The Modular inverses of %s modulo %s is %s" % (a, b, inverseMod(a,b)))

Note that in Python 3.8 onward there's a three argument form of pow that allows calculating the modular inverse simply as pow(a, -1, m). Notably this is efficiently implemented, e.g. pow(10**30, -1, 2**255-19) completes in 5 microseconds.

See: https://docs.python.org/3/library/functions.html#pow