PGCD, théorèmes de Bézout et de Gauss

information-icon

Si tu es un lycéen en terminale, tu dois déjà avoir planifié tes révisions pour ton baccalauréat 2025. Si ce n’est pas le cas, tu peux te baser sur notre programme de révision en le planifiant en fonction des dates du bac 2025 ou des coefficients des matières … 💪

$\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.

Si le $\text{PGCD}(a\ ;\, b)$ est un entier strictement positif
$$\text{PGCD} (a\ ;\,-a)=\vert a\vert$$
$$\text{PGCD} (a\ ;\,1)=1$$
$$\text {PGCD} (a\ ;\,0)=\vert a\vert$$
$$\text{PGCD} (a\ ;\,b)=\text{PGCD} (b\ ;\,a)$$
Les diviseurs communs à $a$ et $b$ sont les diviseurs de leur $\text{PGCD}$
$$\begin{aligned} &\text{PGCD} (ac\ ;\,bc)=c\times\text{PGCD} (a\ ;\,b) \\ &\footnotesize{\textcolor{#A9A9A9}{\text{[pour tout entier naturel non nul $c$]}}} \end{aligned}$$
  • 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$.