PGCD, théorèmes de Bezout et Gauss

Déterminer une solution de l'équation au+bv=1au+bv=1 - Exercice 2

5 min
20
Question 1

Justifier, qu'il existe un couple d'entiers relatifs (u;v)\left(u;v\right) tel que 17u+5v=117u+5v=1 . Trouver un tel couple.

Correction
Theˊoreˋme de Beˊzout\red{\text{Théorème de Bézout}}
  • Deux entiers relatifs aa et bb sont premiers entre eux si et seulement si, il existe deux entiers relatifs uu et vv tels que : au+bv=1au+bv=1
  • Il faut commencer par démontrer que les entiers relatifs 1717 et 55 sont premiers entre eux. Pour cela, il faut calculer le PGCD(17;5)\text{PGCD}\left(17;5\right).
    On vérifie facilement que PGCD(17;5)=1\text{PGCD}\left(17;5\right)=1
    Il en résulte donc que les entiers relatifs 1717 et 55 sont premiers entre eux.
    D’après le Theˊoreˋme de Beˊzout\red{\text{Théorème de Bézout}}, on peut déduire qu’il existe un couple d’entiers relatifs (u;v)\left(u;v\right) tel que 17u+5v=117u+5v=1.
    On cherche un tel couple en utilisant l’algorithme d’Euclide et on isole les restes non nuls obtenus. Il vient alors que :
    17=5×3+217=5\times 3+\pink{2} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad 2=175×3\pink{2}=17-5\times3
    5=2×2+15=2\times 2+\blue{1}     \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \;\; 1=52×2\blue{1}=5-2\times2
    2=1×2+02=1\times 2+0
    Maintenant nous allons remonter l'algorithme d'Euclide en partant du dernier reste non nul :
    1=52×2\blue{1}=5-\pink{2}\times2
    1=5(175×3)×2\blue{1}=5-\pink{\left(17-5\times3\right)}\times2 ( on va à l'étape suivante en réduisant les expressions disposant de la valeur 2525 ) .
    On obtient alors :
    1=517×2+5×3×21=5-17\times2+5\times3\times2
    1=517×2+5×61=5-17\times2+5\times6
    1=17×(2)+5×71=17\times \left(-2\right) +5\times 7
    Il en résulte qu'un couple d'entiers relatifs (u;v)\left(u;v\right) tel que 17u+5v=117u+5v=1 est le couple (2;7)\left(-2;7\right)