Arithmétique/Exercices/Théorème de Bézout

Exercice 6-1

1° En utilisant l'algorithme d'Euclide, trouver une solution de l'équation :

$17x+31y=1$

2° En déduire toutes les solutions de l'équation :

$17x+31y=1$

Solution

1° Effectuons les divisions successives des quotients successifs par les restes successifs :

$31=17\times 1+14$

$17=14\times 1+3$

$14=3\times 4+2$

$3=2\times 1+1$

En repartant de la dernière relation, on obtient :

$1=3-2\times 1=3-(14-3\times 4)\times 1=3\times 5-14=(17-14\times 1)\times 5-14=17\times 5-14\times 6=17\times 5-(31-17\times 1)\times 6=17\times 11-31\times 6$

Nous voyons que nous avons la relation de Bezout :

$17\times 11-31\times 6=1$

Une solution de l'équation :

$17x+31y=1$

est donc :

${\begin{cases}x=11\\y=-6\end{cases}}$

2° Nous avons :

${\begin{cases}17x+31y=1\\17\times 11-31\times 6=1\end{cases}}$

Par soustraction membre à membre, nous obtenons :

$17(x-11)+31(y+6)=0$

qui peut s'écrire :

$31(y+6)=17(11-x)$

Nous en déduisons que 31 divise 17(11-x) tout en étant premier avec 17, donc d'après le théorème de Gauss, 31 divise 11-x. Il existe donc k tel que :

$11-x=31k$

on obtient donc :

$x=11-31k$

En portant cette valeur de x dans :

$17x+31y=1$

on obtient :

$17(11-31k)+31y=1$

qui donne :

$y=17k-6$

On a obtenu :

${\begin{cases}k\in \mathbb {Z} \\x=11-31k\\y=17k-6\end{cases}}$

 

Exercice 6-2

Résoudre l'équation :

$3675x-5145y=4410$.

Solution

En simplifiant par 105, l'équation se réécrit :

$35x-43y=42$,

ou encore :

$35x-43(y+1)=-1$.

Or l'algorithme d'Euclide donne : 1 = 35×16 – 43×13. L'équation équivaut donc à :

$35(x+16)=43(y+14)$,

dont les solutions sont :

$x=-16+43k,\,y=-14+35k\quad (k\in \mathbb {Z} )$.

 

Exercice 6-3

Résoudre l'équation :

$12x-21y=16$

Solution

L'équation peut s'écrire :

$3(4x-7y)=16$

Comme 3 n'est pas un diviseur de 16, nous en déduisons que l'équation n'a pas de solution.

 

Exercice 6-4

Trouvez tous les nombres dont le reste de la division par 13 est 1 et dont le reste de la division par 7 est 6.

Solution

Soit x un des nombres cherchés. Si le reste de sa division par 13 est 1, cela signifie qu'il existe un entier u tel que :

$x=13u+1$.

Si le reste de sa division par 7 est 6, cela signifie qu'il existe un entier v tel que :

$x=7v+6$.

On a alors :

$13u+1=7v+6$,

qui s'écrit :

$13u-7v=5$.

Nous tombons sur une équation dont nous avons vu la méthode de résolution dans les exercices précédents ; on trouve :

${\begin{cases}k\in \mathbb {Z} \\u=7k-5\\v=13k-10\end{cases}}$

et en remplaçant dans les expressions de x, on trouve :

${\begin{cases}k\in \mathbb {Z} \\x=91k-64.\end{cases}}$

Mais une méthode plus efficace est celle des substitutions successives : voir l'exercice 9-10 sur les congruences.