Les théorèmes de Bézout et de Gauss ont de nombreuses applications, en particulier dans les problèmes de chiffrement. Ils permettent, par exemple, d’établir des conditions pour qu’un chiffrement soit utilisable.
I. Définition et propriété
Définition : Deux entiers relatifs non nuls a et b sont premiers entre eux si et seulement si leur PGCD est égal à 1.
Cela revient à dire que le seul diviseur (positif) commun à a et b est 1.
Propriété : Si a et b sont deux entiers relatifs non nuls et d=PGCDa ; b, alors il existe deux entiers relatifs a′ et b′ premiers entre eux tels que a=da′ et b=db′.
II. Théorème de Bézout
Identité de Bézout
Si a et b sont deux entiers relatifs non nuls et d=PGCDa ; b, alors il existe deux entiers relatifs u et v tels que au+bv=d.
Théorème de Bézout
Soit a et b deux entiers relatifs 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.
À noter
Ce théorème a été en réalité démontré par Bachet de Méziriac en 1624. Bézout (1730-1783) l’a ensuite généralisé.
III. Théorème de Gauss
Théorème
a, b et c sont trois entiers relatifs non nuls.
Si a divise bc et a est premier avec b, alors a divise c.
Corollaires
Corollaire 1 : Soit a, b et c trois entiers. Si a et b sont premiers entre eux et divisent c, alors ab divise c.
À noter
Dans ce corollaire, l’hypothèse « a et b sont premiers entre eux » est fondamentale. La conclusion peut être fausse si a et b ne sont pas premiers entre eux. Par exemple, 6 et 4 divisent 60, mais 24 ne divise pas 60.
Corollaire 2 : Si un entier b est premier avec k entiers a1, a2, …, ak, alors b est premier avec le produit a1a2…ak.
Méthode
Résoudre une équation diophantienne
Les équations diophantiennes ont été ainsi nommées en référence au mathématicien grec Diophante d’Alexandrie qui a vraisemblablement vécu au IIIe siècle de notre ère, et a écrit sur ces équations des ouvrages qui ont marqué l’histoire des mathématiques.
On considère l’équation (E) : 7x−11y=3, où x et y sont deux entiers relatifs.
a. Montrer que le couple 13 ; 8 est solution de cette équation.
b. Déterminer toutes les solutions.
Conseils
b. Écrivez que (E) équivaut à 7x−11y=7×13−11×8, puis utilisez le théorème de Gauss.
Solution
a. On a 7×13=91 et 11×8=88, donc 7×13−11×8=3, et le couple 13 ; 8 est solution de l’équation (E).
b. (E) équivaut à 7x−11y=7×13−11×8, soit :
7x−13=11y−8 *.
Donc, si un couple x ; y d’entiers est solution de cette équation, alors 11 divise 7x−13.
Comme 11 est premier avec 7, d’après le théorème de Gauss, 11 divise x−13, donc il existe un entier k tel que x−13=11k, c’est-à-dire x=13+11k.
Alors, en remplaçant dans (*) : 7×11k=11y−8, soit y−8=7k, donc y=8+7k.
Donc tout couple solution est de la forme 13+11k ; 8+7k, avec k∈ℤ.
Réciproquement, si x ; y=13+11k ; 8+7k, avec k∈ℤ, alors :
7x−11y=713+11k−118+7k=91+77k−88−77k, donc 7x−11y=3, donc x ; y est solution de (E).
On en déduit finalement que les solutions de (E) sont les couples 13+11k ; 8+7k, avec k entier relatif.
À noter
On a raisonné par condition nécessaire (tout couple solution vérifie nécessairement…), la réciproque est donc obligatoire.