Retour | Index | Suite

Coéfficients de Bézout (Méthodes classiques).

  • Algorithme d'Euclide (remontée en partant du "bas").

    Exemple 1 :1. Montrer que 38 et 45 sont premiers entre eux à l'aide de l'algorithme d'Euclide.
    2. En remontant cet algorithme, déterminer un couple d'entiers relatifs (x ;y) tel que : 38x + 45y = 1.
    1. L'algorithme d'Euclide s'écrit :
    		 2. Remontée de l'algorithme d'Euclide.
    45 = 1×38 + 7
    38 = 5×7 + 3
    7 = 2×3 + 1
    3 = 3×1 + 0
    		 (a)
    (b)
    (c)
    		 1 = 7 - 2×3
    1 = 7 - 2×(38 - 5×7)
    1 = 11×7 - 2×38
    1 = 11×(45 - 1×38) - 2×38
    1 = - 13×38 + 11×45     		D'après égalité (c)
    car d'après égalité (b) : 3 = 38 - 5×7
     
    car d'après égalité (a) : 7 = 45 - 1×38
    D'où, (x ; y ) = ( -13 ; 11)
    Le PGCD est le dernier reste non nul. PGCD(38 ; 45) = 1.
    Par conséquent, 38 et 45 sont premiers entres eux.

  • Algorithme d'Euclide (remontée en partant du "haut").

    Exemple 2 : 1. Montrer que 41 et 25 sont premiers entre eux à l'aide de l'algorithme d'Euclide.
    2. En remontant cet algorithme, déterminer un couple d'entiers relatifs (x ;y) tel que : 41x - 25y = 1.
    1. L'algorithme d'Euclide s'écrit :
    		 2. Remontée de l'algorithme d'Euclide.
    41 = 1×25 + 16
    25 = 1×16 + 9
    16 = 1×9 + 7
    9 = 1×7 + 2
    7 = 3×2 + 1
    2 = 2×1 + 0
    		 (a)
    (b)
    (c)
    (d)
    (e)     		16 = 1×41 - 1×25
    9 = 1×25 - 1×(1×41 - 1×25)
    9 = -1×41 + 2×25
    7 = 1×(1×41 - 1×25)- 1×(-1×41 + 2×25)
    7 = 2×41 - 3×25
    2 = 1×(-1×41 + 2×25)-1×(2×41 - 3×25)
    2 = -3×41 + 5×25
    1 = 1×(2×41 - 3×25)-3×(-3×41 + 5×25)
    1 = 11×41 - 18×25
    		 D'après égalité (a)
    D'après égalité (b) 9 = 1×25 - 1×16
    ... et en remplaçant 16
    D'après égalité (c) 7 = 1×16 - 1×9
    ... et en remplaçant 16 et 9
    D'après égalité (d) : 2 = 1×9 -1×7
    ... et en remplaçant 9 et 7
    D'après égalité (e) : 1 = 1×7 -3×2
    ... et en remplaçant 7 et 2
    Le PGCD est le dernier reste non nul. Soit PGCD(41;25) = 1.
    Par conséquent, 41 et 25 sont premiers entres eux.
    Au final, on obtient : Le couple (x ; y ) = ( 11 ; 18). Attention aux signes!

    Coéfficients de Bézout (autres méthodes).

  • Algorithme d'Euclide (variante, sans tout réécrire!).

    Une autre méthode pour remonter l'algorithme d'euclide sans avoir à tout réécrire consite à trouver des coefficients pour chaque ligne de l'algorithme de telle sorte que lorsque on les ajoutent membres à menbres les restes soient éliminés.
    Pour cela, il faut commencer par la ligne juste avant celle qui donne le PGCD.
    On détermine par quel nombre on doit la multiplier pour éliminer le reste. On recommence la même opération pour toutes les lignes jusqu'à la première, en faisant attention aux coefficients générés...

    • Exemple 3 : Déterminer une solution particulière de l'équation 199u + 143v = 1.

    199 = 1×143 + 56 × 23 Le premier reste à eliminer est 6. Il apparait 4 fois à la ligne suivante.
    Il faut donc multiplier par -4.
    Le deuxième reste est 25. Il apparait 1 fois à gauche et -4 fois à droite.
    Il faut multiplier la ligne par 5.
    Le troisième reste est 31. Il y en a -4 à gauche et 5 à droite.
    Il faut multiplier la ligne par -9.
    Le quatrième et dernier reste est 56. Il y en a 5 à gauche et 2×(-9) à droite.
    Il faut multiplier la ligne par 23.
    143 = 2×56 + 31 ×(-9)
    56 = 1×31 + 25 × 5
    31 = 1×25 + 6 ×(-4)
    25 = 4×6 + 1
    		  
    6 = 6×1 + 0  

    Finalement, on obtient :
    199×23 + 143×(-9)= 143×23 + 1 soit encore 199×23 + 143×(-32) = 1
    Vérification : 23×199 = 4600-23 = 4577 et 143×32 = 4290+286 = 4576 et 4577 - 4576 = 1 Ok!

  • Autre méthode utile (auteur inconnu).

    Il s'agit d'une version modifiée de l'algorithme d'Euclide avec calcul progressifs des coefficients de Bézout. On part du plus grand nombre entre a et b (a et b étant positifs). On affecte celui-ci des coéfficients 1 et 0. L'autre nombre est affecté des coeffients 0 et 1. On effectue la division euclidienne en la présentant par colonne. On suppose que a > b > 0. Une première colonne contiendra les opposés des quotients, la deuxième a et b, puis les restes. Les deux dernières colonnes contiendront les coefficients. Tout ce passe comme si on écrivait a +(-q)×b = r. On fait la même opération en remplaçant a et b par 1 et 0 (troisième colonne), puis 0 et 1 (quatrième clonne).
    On poursuit en faisant la division euclidienne de b par r, et on calcule les nouveaux coefficients de la même manière que précédemment...
    Le début du tableau ressemble à :
      a 1 0 a = 1×a + 0×b (E1)
    -q b 0 1 b = 0×a + 1×b (E2)
    ? a-q×b = r 1-q×0 = 1 0-q×1= -q a-q×b = (1-q×0)×a + (0-q×1)×b (E1)-q×(E2)
    Cela revient à remonter l'algorihme d'Euclide en partant du haut. Ci-contre, la version non simplifiée correspondante.

    Exemple 4 : Déterminer une solution particulière de l'équation 217u + 34v = 1.
      217 1 0 On obtient ainsi : 217×(-13) + 34×83 = 1

    Vérification : 217×13 = 2170+651 = 2821
    34×83 = 2720+102 = 2822 et -2821 + 2822 = 1 Ok!
    -6 34 0 1
    -2 13 1 -6
    -1 8 -2 13
    -1 5 3 -19
    -1 3 -5 32
    -1 2 8 -51
    (-2) 1 -13 83
      0 34 217