Découvrez le théorème de Bézout, un grand classique en arithmétique qu’il est nécessaire de connaitre pour avoir les bonnes bases.
Prérequis
- Nombres premiers
- Le PGCD
- L’algorithme d’Euclide
Enoncé du théorème de Bézout
Soient a et b deux entiers naturels non nuls.
a et b sont premiers entre eux si et seulement si il existe deux entiers relatifs u et v tels que au + bv = 1
Démonstration du théorème de Bézout
Sens direct : Si au + bv = 1 alors si d est un diviseur commun de a et b, alors d |au + bv = 1 donc d = 1 et a et b sont premiers entre eux.
Sens retour : Si a et b sont premiers entre eux alors on considère A = \{ n = au+bv \in \N , (u,v) \in \Z c’est à dire l’ensemble des entiers naturels non nuls de la forme au+bv avec u et v entiers relatifs. On a a \in A en prenant u=1,v=0. Donc A est une partie non vide de \N . Elle possède donc m = au_1+bv_1, un plus petit élément.
Faisons alors la division euclidienne de a par m . On a donc a = mq +r ce qui nous donne :
\begin{array}{ll}
r&=a-mq \\
& = a-q(au_1+bv_1)\\
&= a(1-qu_1)-qbv_1
\end{array}Par définition 0 \geq r < m . De plus, si r \in A alors m n’est pas le plus petit élément. Donc r=0 . Ainsi, m | a. On obtient par le même raisonnement que m|b . Comme a et b sont premiers, alors nécessairement m =1
Exercices corrigés
Exercice 1
Enoncé : En utilisant l’algorithme d’Euclide, trouver une solution de l’équation 17x+31y=1
Corrigé : On utilise pour commencer l’algorithme d’Euclide :
\begin{array}{lll}
31& =& 17\times 1+14\\
17& =& 14\times 1+3\\
14& =& 3\times 4+2\\
3& =& 2\times 1+1\\
\end{array}Cela suffit pour conclure que 31et 17sont premiers entre eux. Maintenant, on peut remonter l’algorithme d’Euclide :
\begin{array}{lll}
1& =& 3-2\times 1\\
& =& 3-(14-3\times 4)\times 1\\
& =& 3\times 5-14 \times 1\\
& =& (17-14)\times 5-14 \times 1\\
& =& 17\times 5-14 \times 6\\
& =& 17\times 5-(31-17) \times 6\\
& =& 17\times 11-31 \times 6\\
\end{array}Exercice 2
Enoncé : A l’aide de l’algorithme d’Euclide, montrer que 370 et 113 sont premiers entre eux.
En déduire deux entiers u et v tels que 370u+113v=1
Corrigé : C’est le même exercice qu’avant mais avec plus de calculs. On utilise pour commencer l’algorithme d’Euclide :
\begin{array}{lll}
370& =& 113 \times 3+31\\
113& =& 31\times 3+20\\
31& =& 20\times 1+11\\
20& =& 11\times 1+9\\
11& =& 9\times 1+2\\
9& =& 2\times4+1\\
\end{array}Cela suffit pour conclure que 370 et 113 sont premiers entre eux. Maintenant, on peut remonter l’algorithme d’Euclide :
\begin{array}{lll}
1& =& 9-2\times4\\
& =& 9-(11-9\times 1)\times 4\\
& =& 9 \times 5-11 \times 4\\
& =& (20-11\times 1)\times 5-11\times4\\
& =& 20 \times 5- 11 \times 9\\
& =& 20 \times 5 - (31-20\times1) \times 9\\
& =& 20 \times 14 - 31 \times 9\\
& =& (113-31\times 3)\times 14 - 31 \times 9\\
& =& 113\times 14 - 31 \times 51\\
& =& 113\times 14 - (370-113\times 3)\times 51\\
1& =& 113\times 167 - 370\times 51\\
\end{array}u = 51 et v = 167 conviennent
Exercice 3
Enoncé : n est un entier naturel et a = 7n + 4 et b = 5n + 3. Montrer que pour tout n, que a et b sont premiers entre eux
Corrigé : On remarque que 7a -5b = 7 \times (5n+3)- 5 \times (7n+4)= 35n +21-35n -20 = 1 . D’après le théorème de Bézout, on en déduit que a et b sont premiers entre eux.
