Calculer les coefficients de la formule de Bézout   [répertoire]

• Méthode pour Bézout : mêmes calculs que pour le PGCD,
    mais en gardant la décomposition des nombres selon a et b
  au départ : (1,0) = a ; (0,1) = b ; à la fin : PGCD = (x,y) = x a + y b
  somme : (x, y) + (z, t) = (x+z, y+t) ; multiplication : q (x, y) = (qx, qy)
   
• pour les calculs à la main, il vaut mieux présenter (x,y) en vecteur colonne.

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

  
  Calculatrice de relation de Bezout : PGCD_Bezout.html
   
• 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

retour au menu :   pgcd   Arithmétique   Math