Théorèmes de Bezout, Gauss

Théorèmes de Bezout - Gauss

Théorèmes de Bezout et Gauss

Définition

Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$.

 

Théorème de Bezout

Soient $a$ et $b$, deux entiers naturels non nuls.

Si on note $d=PGCD(a;b)$, alors il existe 2 entiers relatifs $u$ et $v$ tels que :

$au+bv=d$

$a$ et $b$ sont premiers entre eux si et seulement si :

$au+bv=1$.

Exemple

Montrer que (2n + 1) et (3n + 2) sont premiers entre eux $forall n in mathbb{N}$.

 

Il s’agit de trouver des coefficients $u$ et $v$ pour que

$u(2n + 1) + v(3n + 2) = 1$.

On choisit astucieusement $u$ et $v$ pour faire disparaître les termes en $n$.

$-3(2n + 1) + 2(3n + 2) = -6n – 3 + 6n + 4 = 1$

$forall n in mathbb{N}$, il existe $u = -3$ et $v = 2$ tel que

$u(2n + 1) + v(3n + 2) = 1$.

Les entiers $(2n + 1)$ et $(3n + 2)$ sont donc premiers entre eux.

 

Théorème de Gauss

Soient $a$, $b$ et $c$, trois entiers relatifs non nuls.

Si $a$ divise $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

 

Exemple 

Trouver (s’ils existent) les couples $(x;y)$ d’entiers solutions de l’équation : $5(x – 1) = 7y$.

5 divise $7y$, or $PGCD(5;7) = 1$, donc d’après le théorème de Gauss, 5 divise $y$.

Il existe donc un entier $k$ tel que : $y = 5k$.

En remplaçant dans l’équation, on a :

$5(x – 1) = 7 times  5k iff x – 1 = 7k iff x = 7k + 1$

Les solutions sont donc de la forme :   $x=7k + 1$ et $y=5k$

On les note $S=left{(7k+1 ; 5k) ; kin mathbb{Z}right}$.

Théorèmes de Bezout - Gauss - Exercice

Exercice : Équations diophantiennes

 

Trouver tous les couples ((x ; y) in mathbb{Z}^2) tels que (12x + 18y = 7).

Étape 1 : On définit rapidement le PGCD du membre de gauche.

Étape 2 : Le PGCD du membre de gauche ne divise pas celui de droite. L’équation n’a pas de solution.