Théorèmes de Bézout et de Gauss

Algorithme d’Euclide

L’algorithme d’Euclide permet de calculer le PGCD de deux nombres $a$​ et $b$​ sans avoir à connaître leur décomposition en facteurs premiers.

Méthode

Exemple

Calcule le PGCD de $133$​  et $77$

Calcule la division euclidienne de $133$  par $77$ :

$133=77×1+56$​​​

Recommence avec $77$  et $56$ :

$77=56×1+21$​​

Recommence avec $56$  et $21$ :

$56=21×2+14$​​

Recommence avec $21$  et $14$ :

$21=14×1+7$​​

Recommence avec $14$  et $7$ :

$14=7×2+0$​​

Le PGCD est donc $7$ .

Définition

On dit que deux nombres entiers sont premiers entre eux si leur PGCD est $1$​ .

Égalité de Bézout

Pour deux entiers relatifs $a$​ et $b$​ dont le PGCD est $d$​, il existe deux entiers relatifs $u$​ et $v$​ tels que :

​$au+bv=d$

​​

Exemple

Le PGCD de $22$​ et $33$​ est $11$​. Tu peux écrire $22×2+33×(-1)=11.$

Théorème de Bézout

Deux entiers relatifs $a$​ et $b$​ sont premiers entre eux si et seulement s’il existe deux entiers relatifs $u$​ et $v$ tels que :

​$au+bv=1$​​

Exemple

$560$​ et $143$​ sont premiers entre eux. En effet, $560×131+143×(-513)=1$​.

Théorème de Gauss

$a, b$​ et $c$​ sont des entiers non nuls. Si $a$​ et $b$​ sont premiers entre eux et si $a$​ divise $b×c,$​  alors $a$​ divise $c$​.

Exemple

$3$​ divise $42=6×7$​ mais ne divise pas $7$​ ($3$​ et $7$​ sont premiers entre eux), donc $3$​ divise $6$​.

Équations diophantiennes

Les équations diophantiennes sont des équations de la forme $ax+by=c$​  où tous les coefficients et variables sont des entiers relatifs. Une équation diophantienne avec $a$​ et $b$​ non simultanément nuls possède des solutions si et seulement si $c$​ est un multiple du PGCD de $a$ et $b$​.

Exemples

L’équation diophantienne $133x+77y=14$ possède des solutions, puisque $PGCD(133;77)=7$​  et $14$​ est un multiple de $7$​. Une solution est par exemple $x=3$​  et $y=-5$​ .

L’équation diophantienne $11x+22y=7$​ ne possède pas de solution, puisque $PGCD(11;22)=11$​ ne divise pas $7$​.

Résoudre une équation diophantienne

Méthode

Exemple 

Trouve des solutions entières de l’équation $4x+5y=23$​ .

Comme $4$​ et $5$​ sont premiers entre eux, leur PGCD vaut $1$​. $23$​ est un multiple de $1$​. Donc l’équation diophantienne possède des solutions.

Isole $y$​ :

$y=\frac{23-4x}{5}$

​​

Cherche un $x$​ pour que $23-4x$​  soit un multiple de $5$​ :

$x=2⇒23-4×2=15$

​​

Retrouve la valeur de $y$​ :

​$y= \frac{23-4×2}{5}=3$

​​

Donc $(x=2,y=3)$​  est solution de l’équation diophantienne.