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.