def ExtendedEuclideanAlgorithm(a, b):
	"""
		Calculates gcd(a,b) and a linear combination such that
		gcd(a,b) = a*x + b*y

		As a side effect:
		If gcd(a,b) = 1 = a*x + b*y
		Then x is multiplicative inverse of a modulo b.
	"""
	aO, bO = a, b

	x=lasty=0
	y=lastx=1
	while (b!=0):
		q= a/b
		a, b = b, a%b
		x, lastx = lastx-q*x, x
		y, lasty = lasty-q*y, y

	return {
		"x": lastx,
		"y": lasty,
		"gcd": aO * lastx + bO * lasty
	}