def extended_gcd(a, b):
	"""
	We know:
		ax + by = gcd(a, b)
	
	This function returns gcd(a,b), x , y 	
	"""

	if a == 0:
		return b, 0, 1
	gcd, x_, y_ = extended_gcd(b % a, a)

	x = y_ - (b // a) * x_
	y = x_

	return gcd, x, y