Calculer le PGCD de 2 nombres ou
les coefficients de la formule de Bézout   [répertoire]

a =     b =
       
Calculs :

Méthode : soit (x,y) = x a + y b
a = (1,0) ; b = (0,1)
pour les calculs à la main, il vaut mieux présenter (x,y) en colonne.

a = b q0 + r0	⇒	r0 = a − q0 b	= (1,0) − q0 (0,1) = (1,−q0)	r0 = (1,−q0)
b = r0 q1 + r1	⇒	r1 = b − q1 r0	= (0,1) − q1 (1,−q0) = (−q1, 1+q1q0)	r1 = (−q1, 1+q1q0)
r0 = r1 q2 + r2	⇒	r2 = r0 − q2 r1	= (1,−q0) − q2 (−q1, 1+q1q0)	r2 = (1+q2q1, −q0 − q2 − q2q1q0)

Exemple : avec 2 nombres de Fibonacci successifs : a=89=(1,0)   ;   b=55=(0,1)

89 = 1 * 55 + 34	⇒	34 = 89 − 55	34 = (1, −1)
55 = 1 * 34 + 21	⇒	21 = 55 − 34 = (0,1) − (1, −1)	21 = (−1, 2)
34 = 1 * 21 + 13	⇒	13 = 34 − 21 = (1, −1) − (−1, 2)	13 = (2, −3)
21 = 1 * 13 + 8	⇒	8 = 21 − 13 = (−1, 2) − (2, −3)	8 = (−3, 5)
13 = 1 * 8 + 5	⇒	5 = 13 − 8 = (2, −3) − (−3, 5)	5 = (5, −8)
8 = 1 * 5 + 3	⇒	3 = 8 − 5 = (−3, 5) − (5, −8)	3 = (−8, 13)
5 = 1 * 3 + 2	⇒	2 = 5 − 3 = (5, −8) − (−8, 13)	2 = (13, −21)
3 = 1 * 2 + 1	⇒	1 = 3 − 2 = (−8, 13) − (13, −21)	1 = (−21, 34)
Bézout : 1 = (−21) × 89 + 34 × 55