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

1.

Calcule la division euclidienne de $a$ par $b$ .

$a=q×b+r$

2.

Recommence en calculant la division euclidienne de $b$ par $r$ :

$b=q'×b+r'$

3.

Continue jusqu’à obtenir un reste nul. Le dernier reste non nul trouvé est le PGCD.

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

1.

Isole $y$ dans l’équation $ax+by=c$ :

$y=\frac{c-ax}{b}$

2.

Cherche un $x$ tel que $c-ax$ est un multiple de $b$ .

3.

Vérifie les solutions.

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.