gcd.py

def extend_gcd(a,b):
    if b==0:
        return a,1,0
    else:
        g,s,t=extend_gcd(b,a%b)
        return g,t,s-a/b*t

def reverse(a,N):
    return extend_gcd(a,N)[1]
 
print reverse(5,7)