Arithmétique PGCD et PPCM Recherche d'entiers u et v

précédent

 suivant résumé résumé

Recherche d'entiers u et v tels que au + bv = d :

L'algorithme d'Euclide nous fournit une méthode simple pour trouver deux entiers u et v apparaissant dans le théorème de Bézout. Illustrons-le tout de suite sur l'exemple précédent.

a =7b+r1 a - 7b = r1
b = 2r1+r2 b - 2(a - 7b) = r2
  15b - 2a = r2
r1 = r2 + r3 r1 - r2 = r3
 (a - 7b) - (15b - 2a) = r3
  3a-22b = r3
    3a - 22b = d

On a donc trouvé un couple d'entiers (3, -22) tels que :

3 × 95991 - 22 × 13083 = 147

Bien sûr, il n'y a pas unicité de ce couple car on voit tout de suite que :

(3 + 13083 k) × 95991 - (22 + 95991 k) × 13083 = 147, si k est un entier quelconque. Nous reviendrons sur cet exemple ultérieurement pour chercher tous les couples répondant au problème.

Arithmétique PGCD Théorème de Bézout

précédent

 suivant résumé résumé