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 Bézout :

$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}}$

 

Résoudre de même dans $\mathbb {Z}$ :

$36x-415y=1$.

Solution

L'algorithme d'Euclide donne

$415=36\times 11+19,36=19\times 1+17,19=17\times 1+2,17=2\times 8+1$

puis en remontant :

$1=17-2\times 8=17-(19-17)\times 8=17\times 9-19\times 8=(36-19)\times 9-19\times 8=36\times 9-19\times 17=36\times 9-(415-36\times 11)\times 17=36\times 196-415\times 17$.

Par conséquent,

$36x-415y=1\Leftrightarrow 36x-415y=36\times 196-415\times 17\Leftrightarrow 36(x-196)=415(y-17)\Leftrightarrow x=196+415k,\;y=17+36k\;(k\in \mathbb {Z} )$.

 

Exercice 6-2

Résoudre l'équation :

$3675x-5145y=4410$.

Solution

On peut remarquer que :

$3675=5^{2}*7^{2}*3$,

$5145=5*3*7^{3}$,

$4410=5*2*3^{2}*7^{2}$,

En simplifiant par : $5*7^{2}*3=735$, l'équation se réécrit :

$5x-7y=6$.

Une solution évidente est x=4 et y=2 L'équation équivaut donc à :

$5(x-4)=7(y-2)$,

dont les solutions sont :

$x=4+7k,\,y=2+5k\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, 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.

 

Trouver de même :

1. tous les nombres dont le reste de la division par 4 est 3 et dont le reste de la division par 7 est 4 ;
2. tous les nombres dont le reste de la division par 6 est 4 et dont le reste de la division par 15 est 8 ;
3. tous les nombres dont le reste de la division par 4 est 1 et dont le reste de la division par 7 est 4 ;
4. tous les nombres dont le reste de la division par 5 est 4, dont le reste de la division par 6 est 3 et dont le reste de la division par 7 est 2.

Solution

1. On cherche les couples d'entiers $(u,v)$ tels que $4u+3=7v+4$, c'est-à-dire $4u-7v=1$. On trouve une solution particulière de l'identité de Bézout grâce à l'algorithme d'Euclide étendu : $7=4\times 1+3$, $4=3\times 1+1$, donc en remontant : $1=4-3=4-(7-4)=4\times 2-7\times 1$, donc l'équation initiale $4u-7v=1$ équivaut à $4u-7v=4\times 2-7\times 1$, c'est-à-dire $4(u-2)=7(v-1)$ et les solutions sont : $u=7k+2$ et $v=4k+1$, soit finalement $n=4u+3=7v+4=28k+11$ ($k\in \mathbb {Z}$).
   Autre méthode : parmi les entiers de 0 à 27, ceux qui sont congrus à 4 mod 7 sont 4, 11, 18, 25 et ceux congrus à 3 mod 4 sont 3, 10, 11, 15, 19, 23, 27. On a la solution en prenant l'intersection : $n\equiv 11{\bmod {28}}$.
2. $6u+4=15v+8\Rightarrow 3(2u-5v)=4$ : pas de solution.
3. $4u+1=7v+4\Leftrightarrow 4u-7v=3=3(4\times 2-7\times 1)=4\times 6-7\times 3\Leftrightarrow 4(u-6)=7(v-3)$ et les solutions sont : $u=7k+6$ et $v=4k+3$, soit finalement $n=4u+1=7v+4=28k+25$ ($k\in \mathbb {Z}$).
   Autre méthode : parmi les entiers de 0 à 27, ceux qui sont congrus à 4 mod 7 sont 4, 11, 18, 25 et parmi eux, le seul congru à 1 mod 4 est 25…
4. $5u+4=6v+3\Leftrightarrow 5u-6v=-1=5-6\Leftrightarrow 5(u-1)=6(v-1)\Leftrightarrow u=6k+1,v=5k+1,n=5u+4=6v+3=30k+9\;(k\in \mathbb {Z} )$, puis $30k+9=7w+2\Leftrightarrow 30k-7w=-7\Leftrightarrow k=7l,w=30l+1,n=30k+9=7w+2=210l+9\;(l\in \mathbb {Z} )$.

 

Exercice 6-5

Résoudre dans $\mathbb {Z} ^{3}$ : $35x+55y+77z=1$. $\operatorname {pgcd} (35,55)=5=55\times 2-35\times 3$ et $\operatorname {pgcd} (5,77)=1=5\times 31-77\times 2$ donc

Solution

une solution est $(x_{0},y_{0},z_{0})=(-3\times 31,2\times 31,-2)=(-93,62,-2)$.

Les autres sont données par $(x,y,z)=(x_{0},y_{0},z_{0})+(p,q,r)$ avec $35p+55q+77r=0$, c'est-à-dire $p=11i,q=7j,r=-5(i+j),(i,j)\in \mathbb {Z} ^{2}$.

 

Lien externe

« Calculatrice de l'identité de Bézout », sur dcode.fr