Théorème de Bézout
Théorème :
Soient \(a\) et \(b\) deux entiers naturels et \(d\) leur pgcd alors il existe au moins un couple d'entiers relatifs \(u\) et \(v\) tel que \(ua + vb = d.\)
Recherche d'entiers u et v tels que au + bv = d
L'algorithme d'Euclide nous fournit une méthode simple pour trouver deux entiers \(u\) et \(v\) apparaissant dans le théorème de Bézout. Illustrons-le tout de suite sur l'exemple précédent.
\(a =7b+r_1\) | \(a - 7b = r_1\) |
\(b = 2r_1+r_2\) | \(b - 2(a - 7b) = r_2\) |
\(15b - 2a = r_2\) | |
\(r_1 = r_2 + r_3\) | \(r_1 - r_2 = r_3\) |
\((a - 7b) - (15b - 2a) = r_3\) | |
\(3a-22b = r_3\) | |
\(3a - 22b = d\) |
On a donc trouvé un couple d'entiers \((3, -22)\) tels que :
\(3 × 95991 - 22 × 13083 = 147\)
Bien sûr, il n'y a pas unicité de ce couple car on voit tout de suite que :
(3 + 13083 \(k)\) × 95991 - (22 + 95991 \(k)\) × 13083 = 147, si \(k\) est un entier quelconque. Nous reviendrons sur cet exemple ultérieurement pour chercher tous les couples répondant au problème.
Remarque : entiers u et v
On sait que le pgcd divise chacun des deux nombres ;
95991 = 147 × 653 et 13083 = 147 × 89.
Remarquons tout de suite que le couple d'entiers (3, -22) vérifie la relation obtenue en simplifiant par 147 la relation précédente :
\(\begin{array}{ccc}3 × 95991 - 22 × 13083&=&147\\3 × 653 - 22 × 89&=&1\end{array}\)
Ceci nous sera utile plus tard. Nous allons faire une deuxième démonstration du théorème de Bézout, reposant sur des principes très différents, et en donner un énoncé un peu plus complet.
Théorème :
Soient deux entiers relatifs \(a\) et \(b\) non nuls, et \(d\) leur pgcd. Alors
il existe deux entiers relatifs \(x_0\) et \(y_0\) tels que pgcd\((a,b)= ax_0+by_0 ;\)
l'ensemble \(S= { ax+by \mid x,y \in \mathbb Z}\) est l'ensemble des multiples de \(d.\)
Représentons pour différentes valeurs de \(a\) et \(b\) l'ensemble :
\(\{ax + by -n \leq x \leq n -n \leq y \leq n\} .\)
Observez sur les exemples les valeurs du tableau en cherchant quelle est la plus petite valeur positive du tableau et quel est le pgcd de \(a\) et \(b .\)
Le programme suivant permet de visualiser différentes valeurs de \(ax + by,\) où \(a\) et \(b\) sont deux entiers, et \(x\) et \(y\) sont des entiers compris entre \(- n\) et \(+ n .\)
Testez les valeurs suivantes puis d'autres de votre choix. Les exemples qui vous sont proposés permettent de faire apparaître le pgcd de \(a\) et \(b\) pour une petite valeur de \(n.\)
Attention au temps de calcul, prenez de petites valeurs pour \(n\) !!!
\(a = 26\) \(b = 22\) \(n = 8\)
\(a = 135\) \(b = 195\) \(n = 5\)
\(a = 71\) \(b = 95\) \(n = 5\)
\(a =\)
\(b =\)
\(n =\)
Détermination de l'ensemble S
Soient deux entiers relatifs \(a\) et \(b\) non nuls, \(ab \neq 0.\) Considérons l'ensemble \(S'\) des entiers positifs qui peuvent s'écrire sous la forme \(ax + by :\)
\(S' = \{ ax + by \mid x, y \in \mathbb Z \quad \textrm {et} \quad ax + by > 0 \}.\)
De façon évidente \(S'\) est non vide puisque l'un des nombres au moins \(\pm a,\pm b\) est positif. D'après la propriété du bon ordre, cet ensemble possède un plus petit élément \(d.\) Il existe deux entiers relatifs \(x_0 et y_0\) tels que \(d = x_0a + y_0b.\)
Montrons que ce nombre \(d\) est le pgcd des deux nombres \(a\) et \(b.\)
On va d'abord montrer que \(d \mid a\) et \(d \mid b.\) Sinon, on peut écrire la division euclidienne de \(a\) par \(d\) avec un reste non nul : \(a = dq + r\) avec \(0 < r < d.\) Comme \(d = x_0 a + y_0 b , r = a - (x_0 a + y_0 b)q = a(1 - x_0 q) - b y_0 q,\) ce qui montre que \(r\) appartient à l'ensemble \(S'\) et est plus petit que \(d,\) ce qui est contraire à la définition de \(d.\) On en conclut que \(d\) divise \(a.\) De la même façon, on montre que \(d\) divise \(b\) et donc que \(d\) est un diviseur commun à \(a\) et \(b.\)
On va maintenant montrer que \(d\) est le pgcd de \(a\) et \(b :\) dans les propriétés sur la divisibilité, on a montré que tout diviseur commun à \(a\) et \(b\) divise tous les éléments de \(S\) et donc en particulier \(d.\) Ceci démontre que \(d\) est le plus grand diviseur commun de \(a\) et de \(b.\)
Nature de l'ensemble S
Tous les entiers de la forme \(ax + by\) sont des multiples du pgcd de \(a\) et \(b.\) Il est évident que tout multiple de d appartient à \(S :\)
\(m(ax_0 + by_0) = a(mx_0) + b(my_0)\)
Par ailleurs \(d\) divisant \(a\) et \(b,\) il divise tous les entiers de la forme \(ax + by.\) On a donc montré que l'ensemble \(S\) est constitué des multiples de \(d.\)
Remarque :
\(u\) et \(v\) ne sont pas uniques. Par exemple, \(u + kb\) et \(v - ka\) répondent aussi au problème.
Attention :
S'il existe un couple d'entiers \(u\) et \(v\) tels que \(au + bv = d',\) on peut seulement conclure que \(d'\) est un multiple du pgcd de \(a\) et \(b.\) En général, le théorème de Bézout n'admet pas de réciproque sauf dans le cas particulier des nombres premiers entre eux que nous étudions dans le chapitre suivant.