euclide.py

'''
	Description : Calcule le PGCD de deux nombres et leurs
	coefficients de bezout
	Return : PGCD, Coef de X, Coef de Y 
	(X est le nombre le plus grand)
'''
def pgcd_etendu(a, b):
	a, b = abs(a), abs(b)
	# On s'assure que le plus grand nombre est a
	#if b > a:
		#b,a = a,b

	# Vérification que le plus petit nombre n'est pas 0
	assert(not (b == 0))

	r = [None] * 100
	q = [None] * 100
	x = [None] * 100
	y = [None] * 100
	etape = 2

	# Phase d'initialisation
	r[0] = a
	x[0] = 1
	y[0] = 0

	r[1] = b
	x[1] = 0
	y[1] = 1

	while (r[etape-1] != 0):
		r[etape] = a % b
		q[etape] = a // b
		x[etape] = x[etape-2] - q[etape] * x[etape-1]
		y[etape] = y[etape-2] - q[etape] * y[etape-1]

		a, b = b, r[etape]
		etape += 1

	return r[etape-2], x[etape-2], y[etape-2]

def pgcd_etendu_verif(a, b, x, y, pgcd):
	if (pgcd == (a*x + b*y)):
		return True

	return False

if __name__ == '__main__':

	b = 4991
	a = 1197

	print(pgcd_etendu(a, b))
	pgcd, x, y = pgcd_etendu(a, b)
	print(pgcd_etendu_verif(a, b, x, y, pgcd))