Uses the extended euclidian algorithm to find the multiplicative inverse of two numbers, a and b.

euclid-extended.py

# If a and b are positive integers, then there are always integers m and n so that the GCD of a and b equals m·a+n·b.
# i.e., Since the GCD of 210 and 45 is 15, we should be able to write 15 as a sum of multiples of 210 and 45.
# Finding multiplicative inverses mod p

a = 3276
b = 29

print("Finding Multiplicative Inverse of", a, "and", b)
if a < b:
    temp = a
    a = b
    b = temp

t1 = 0
t2 = 1
t = 0

found = False
while not found:
    if b == 0:
        print("Multiplicative Inverse:", t1)
        found = True
        break

    q = a // b #floor division (aka integer division)
    r = a % b
    t = t1 - (t2 * q)
    
    a = b
    b = r

    t1 = t2
    t2 = t