Fiche de révision : PGCD, théorèmes de Bézout et de Gauss

$\text{PGCD}$ et algorithme d’Euclide

• Pour tout entier naturel $a$, on note $\text D(a)$ l’ensemble des diviseurs de $a$.
• L’ensemble $\text D(a)$ contient toujours au moins $1$ et $a$ lui-même.
• Le plus grand élément des diviseurs de $a$ est $a$ (quand $a\neq 0$).
• Pour tous entiers naturels $a$ et $b$ non nuls, on note $\text D(a\ ;\,b)$ l’ensemble des diviseurs communs à $a$ et à $b$.
• $\text D(a\ ;\,b)$ est non vide puisqu’il contient toujours au moins $1$.
• Tous les nombres que contient $\text D(a\ ;\,b)$ sont inférieurs ou égaux à $a$ et à $b$.
• $a$ et $b$ sont deux entiers naturels non nuls.
• Le plus grand élément de $\text D(a\ ;\,b)$ est appellé plus grand commun diviseur de $a$ et $b$, noté : $\text{PGCD} (a\ ;\,b) $.
• Cette définition peut s’étendre aux entiers relatifs. Dans le cas d’entiers négatifs, nous nous ramenons à des entiers positifs en prenant leurs valeurs absolues : $\text{PGCD}(a\ ;\,b)=\text{PGCD}(\vert a \vert\ ;\,\vert b \vert)$.
• Si $a$ divise $b$ : $\text{PGCD} (a\ ;\,b)=\vert a\vert$.
• $a$ et $b$ sont deux entiers naturels supérieurs ou égaux à $2$.
• Si, dans leur décomposition en produit de facteurs premiers, $a$ et $b$ n’ont pas de facteur premier commun : $\text {PGCD}(a\ ;\,b)=1$.
• Sinon, le $\text {PGCD}$ de $a$ et de $b$ est égal au produit des facteurs premiers communs à $a$ et à $b$, chacun d’eux étant affecté du plus petit exposant figurant dans la décomposition de $a$ et dans celle de $b$.
• $a$ et $b$ sont deux entiers relatifs non nuls.

• Algorithme d’Euclide : $a$ et $b$ sont deux entiers naturels non nuls tels que la division euclidienne de $a$ par $b$ se traduit par $a=bq+r$, avec $0 \leq r < b$.
• L’ensemble des diviseurs communs à $a$ et $b$ est identique à ceux communs à $b$ et $r$ :

$$\begin{aligned} \text D(a\ ;\,b)&=\text D(b\ ;\,r) \\ \text{PGCD}(a\ ;\,b)&=\text{PGCD}(b\ ;\,r) \end{aligned}$$

• Lorsque $b$ ne divise pas $a$, le $\text{PGCD}$ de $a$ et $b$ est le dernier reste non nul dans la succession des divisions de l’algorithme d’Euclide.
• Dire que deux entiers naturels non nuls $a$ et $b$ sont premiers entre eux signifie que leur $\text{PGCD}$ est égal à $1$.
• Dire que $d$ est le $\text {PGCD}$ de $a$ et $b$ équivaut à dire qu’il existe deux entiers naturels $a^{\prime}$ et $b^{\prime}$ tels que :

$$\begin{aligned} a &= da^{\prime} \\ b &= db^{\prime} \\ \text {PGCD} (a^{\prime}\ ;\,b^{\prime}) &= 1 \end{aligned}$$

• $\text {PGCD} (a^{\prime}\ ;\, b^{\prime}) = 1$ signifie que $a^{\prime}$ et $b^{\prime}$ sont premiers entre eux, c’est-à-dire qu’ils n’ont aucun diviseur en commun autre que $1$.
• Pour deux entiers naturels non nuls $a$ et $n$, si $a$ et $n$ sont premiers entre eux, alors $a$ admet un inverse modulo $n$, c’est-à-dire qu’il existe un entier relatif $x$ tel que : $ax \equiv 1 \,\lbrack n\rbrack$.

Théorème de Bézout

• Égalité de Bézout : Soit $a$ et $b$ sont deux entiers relatifs non nuls, et $d$ leur $\text{PGCD}$.
• 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.
• Dire que $a$ et $b$ sont premiers entre eux équivaut à dire qu’il existe deux entiers relatifs $u$ et $v$ tels que $au+bv = 1$.
• En pratique, pour trouver $u$ et $v$, on utilise d’abord l’algorithme d’Euclide pour démontrer que les deux nombres sont premiers entre eux.
  Puis, on reprend chaque division euclidienne pour exprimer chaque reste au fur et à mesure.
  On trouve ainsi le couple solution.

Théorèmes de Gauss et équation diophantienne

• Théorème de Gauss : Soit $a$, $b$ et $c$ des entiers naturels non nuls.
• Si $a$ divise le produit $bc$ tout en étant premier avec $b$, alors $a$ divise $c$.
• Autrement dit, si un entier naturel divise un produit de deux facteurs et s’il est premier avec l’un d’eux, il divise l’autre.
• Corollaires du théorème de Gauss :
• Si un entier relatif $n$ est divisible par deux entiers relatifs $a$ et $b$ premiers entre eux, il est divisible par leur produit.
• Si un nombre premier $p$ divise un produit $ab$, alors $p$ divise $a$ ou $p$ divise $b$.
• Entre autres, on se sert de ces notions dans la résolution d’équations diophantiennes.
• Une équation diophantienne est une équation de la forme $ax+by=c$ où les coefficients $a$, $b$ et $c$ sont des nombres entiers relatifs et dont les solutions recherchées $x$ et $y$ sont également des entiers relatifs.
• Pour que l’équation diophantienne $ax+by=c$ admette des solutions, il faut que $c$ soit un multiple de $d = \text{PGCD}(a\ ;\,b)$.
• Pour résoudre une telle équation diophantienne, en admettant que $a$ et $b$ sont premiers entre eux :
• on identifie une solution particulière $(x_0\ ;\, y_0)$ ;
• on se sert de cette solution particulière et du théorème de Gauss pour déterminer l’ensemble solution.
• Exemple méthodologique : Résolution de l’équation diophantienne $2x+3y=1$.
• $(\blue {-1}\ ;\, \green 1)$ est solution particulière de cette équation.
• $2x + 3y = 2\times(\blue{-1})+ 3\times \green 1\Leftrightarrow 2(x +\blue 1) = 3(-y +\green1)$.
• $3$ divise $2(x +1)$.
• Comme $3$ est premier avec $2$, d’après le théorème de Gauss, $3$ divise $(x + 1)$.
• Il existe donc un entier relatif $k$ tel que $x + 1 = 3k$, soit $x = -1+ 3k$.
• En reportant la valeur de $x$ dans l’égalité $2(x +1) = 3(-y +1)$, on obtient : $y = 1- 2k$.
• Réciproquement, si $x = -1+ 3k$ et $y = 1- 2k$, pour $k$ un entier relatif :

$$2x+3y =2(-1+3k)+3(1-2k)=1$$

• Les solutions de cette équation sont les couples $(-1+3k\ ;\,1-2k)$, avec $k\in\mathbb Z$.