def egcd(a,b)
	# Extended Euclidean Algorithm
	# returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
	u, u1 = 1, 0
	v, v1 = 0, 1
	while b
		q = a / b
		u, u1 = u1, u - q * u1
		v, v1 = v1, v - q * v1
		a, b = b, a - q * b
	end
	[u, v, a]
end

def modInverse(e,n)
	# d such that de = 1 (mod n)
	# e must be coprime to n
	# this is assumed to be true
	egcd(e,n)[0]%n
end