Resolve "Create Function find_p_q"

Closes #2 (closed)

src/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))
\ No newline at end of file