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 = PGCD (a; b)$ , alors il existe deux entiers relatifs $a^{'}$ et $b^{'}$ premiers entre eux tels que $a = d a^{'}$ et $b = d b^{'}$ .

II) Théorème de Bézout

Identité de Bézout

Si a et b sont deux entiers relatifs non nuls et $d = PGCD (a; b)$ , alors il existe deux entiers relatifs u et v tels que $a u + b v = 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 $a u + b v = 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 $a_{1}$ , $a_{2}$ , …, $a_{k}$ , alors b est premier avec le produit $a_{1} a_{2} \dots a_{k}$ .

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 III^e 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) : $7 x - 11 y = 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 à $7 x - 11 y = 7 \times 13 - 11 \times 8$ , puis utilisez le théorème de Gauss.

Solution

a. On a $7 \times 13 = 91$ et $11 \times 8 = 88$ , donc $7 \times 13 - 11 \times 8 = 3$ , et le couple $(13; 8)$ est solution de l’équation (E).

b. (E) équivaut à $7 x - 11 y = 7 \times 13 - 11 \times 8$ , soit :

$7 (x - 13) = 11 (y - 8) (*) .$

Donc, si un couple $(x; y)$ d’entiers est solution de cette équation, alors 11 divise $7 (x - 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 = 11 k$ , c’est-à-dire $x = 13 + 11 k$ .

Alors, en remplaçant dans (*) : $7 \times 11 k = 11 (y - 8)$ , soit $y - 8 = 7 k$ , donc $y = 8 + 7 k$ .

Donc tout couple solution est de la forme $(13 + 11 k; 8 + 7 k)$ , avec $k \in ℤ$ .

Réciproquement, si $(x; y) = (13 + 11 k; 8 + 7 k)$ , avec $k \in ℤ$ , alors :

$7 x - 11 y = 7 (13 + 11 k) - 11 (8 + 7 k) = 91 + 77 k - 88 - 77 k$ , donc $7 x - 11 y = 3$ , donc $(x; y)$ est solution de (E).

On en déduit finalement que les solutions de (E) sont les couples $(13 + 11 k; 8 + 7 k)$ , 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.

Entiers premiers entre eux