CoursTerminale maths expertes
PGCD, Bézout, Gauss et équations diophantiennes
PGCD et entiers premiers entre eux
Pour deux entiers $a,b$ non simultanément nuls, $\operatorname{PGCD}(a,b)$ est leur plus grand diviseur commun positif. Les signes ne changent pas le PGCD :
On pose ici par convention $\operatorname{PGCD}(0,0)=0$. Deux entiers sont premiers entre eux lorsque leur PGCD vaut $1$ ; ils ne sont pas nécessairement premiers individuellement.
Calculer le PGCD par Euclide
Si $a\geq0$, $b>0$ et $a=bq+r$ avec $0\leq r<b$, alors $\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,r)$. Effectuer des divisions successives, en remplaçant $(a,b)$ par $(b,r)$, jusqu'au reste nul.
Le PGCD est le dernier reste non nul, ou le premier diviseur si la première division est exacte. Pour des entiers négatifs, commencer par leurs valeurs absolues ; si le second entier est nul, utiliser la convention précédente.
Bézout et inverse modulaire
Pour $a,b\in\mathbb Z$ non simultanément nuls et $d=\operatorname{PGCD}(a,b)$, il existe $u,v\in\mathbb Z$ tels que $au+bv=d$. Un tel couple de Bézout n'est pas unique.
Pour le trouver, remonter les divisions d'Euclide. Dans l'exemple précédent :
Théorème de Bézout : $a,b$ sont premiers entre eux si et seulement s'il existe des entiers $u,v$ tels que $au+bv=1$.
Pour $n\geq2$, $a$ possède un inverse modulo $n$ si et seulement si $\operatorname{PGCD}(a,n)=1$. Une identité $au+nv=1$ donne l'inverse $u$ puisque $au\equiv1\pmod n$.
Voir un exemple — Trouver l’inverse de 17 modulo 43
Un inverse de 17 modulo 43
$43=2\times17+9$, $17=9+8$ et $9=8+1$ montrent que $\operatorname{PGCD}(17,43)=1$. La remontée donne $1=2\times43-5\times17$.
$-5\equiv38\pmod{43}$ : l'inverse recherché entre $0$ et $42$ est $38$. Le contrôle $17\times38=646=15\times43+1$ confirme la congruence.
Appliquer le théorème de Gauss
Pour $a,b,c\in\mathbb Z$, si $a\mid bc$ et $\operatorname{PGCD}(a,b)=1$, alors $a\mid c$. Vérifier les deux hypothèses avant d'éliminer le facteur $b$.
La coprimalité est indispensable : $6\mid3\times4$, mais $6\nmid4$.
Si deux entiers positifs $b,c$ premiers entre eux divisent $N$, alors $bc\mid N$.
Comprendre pourquoi — Comment Bézout démontre Gauss
Comme $a$ et $b$ sont premiers entre eux, Bézout fournit des entiers $u,v$ tels que
En multipliant par $c$, on obtient
Or $a$ divise $auc$. Il divise aussi $bvc$, puisque $a$ divise $bc$ par hypothèse. Il divise donc leur somme, qui est $c$.
Équations à solutions entières
Pour $a,b,c\in\mathbb Z$, $a,b$ non simultanément nuls, l'équation $ax+by=c$ admet une solution entière si et seulement si $\operatorname{PGCD}(a,b)\mid c$. Une solution réelle ou rationnelle ne suffit pas.
Une identité de Bézout $au+bv=d$ fournit une solution particulière en multipliant $u,v$ par l'entier $\frac{c}{d}$, lorsque $d\mid c$.
Voir un exemple — Résoudre une équation simple
Pour $7x+11y=100$, $(8,4)$ est une solution. Comparer toute autre solution à celle-ci donne $7(x-8)=-11(y-4)$. Gauss impose $11\mid(x-8)$, donc :
En remplaçant dans l'équation, on vérifie que tous ces couples conviennent.
Comprendre pourquoi — Pourquoi le PGCD décide de l’existence
Soient $a,b,c\in\mathbb Z$, $a,b$ non simultanément nuls, et $d=\operatorname{PGCD}(a,b)>0$. Si $ax+by=c$ pour des entiers $x,y$, alors $d$ divise $ax$ et $by$, donc $c$.
Réciproquement, si $d\mid c$, écrire $c=kd$ avec $k\in\mathbb Z$. Bézout fournit des entiers $u,v$ tels que $au+bv=d$. Alors :
Le couple $(ku,kv)$ est entier et résout l'équation. La condition $d\mid c$ est donc nécessaire et suffisante.