Implementation of inverse element algorithm in Python

# Extend Euclid to find the inverse element 
def exgcd(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = exgcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y, q
# Extend Euclid to find the inverse element 
def ModReverse(a,p):
x, y, q = exgcd(a,p)
if q != 1:
raise Exception("No solution.")
else:
return (x + p) % p # Prevent negative numbers