# 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$.
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$.
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$.
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$.
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.
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 :
* tous les nombres dont le reste de la division par 4 est 3 et dont le reste de la division par 7 est 4 ;
* tous les nombres dont le reste de la division par 6 est 4 et dont le reste de la division par 15 est 8 ;
* tous les nombres dont le reste de la division par 4 est 1 et dont le reste de la division par 7 est 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.
* 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}}$.
* $6u+4=15v+8\Rightarrow 3(2u-5v)=4$ : pas de solution.
* $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…
* $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
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
| Théorème de Gauss | Fractions |