Chapitre 22 — l'algorithme d'Euclide, les théorèmes de Bézout et de Gauss, et la résolution des équations $ax+by=c$.
Naviguez avec les flèches ← → du clavier, ou via le Sommaire.
Tout repose sur l'algorithme d'Euclide et la combinaison linéaire : du calcul du pgcd jusqu'aux équations diophantiennes.
Pour $a,b\in\mathbb{Z}^*$, le pgcd de $a$ et $b$ est le plus grand élément de $\operatorname{Div}(a)\cap\operatorname{Div}(b)$. On le note $\operatorname{pgcd}(a,b)$ ou $a\wedge b$.
$\operatorname{Div}(63)\cap\operatorname{Div}(45)=\{\pm1,\pm3,\pm9\}$, donc $\operatorname{pgcd}(63,45)=9$.
Si $a\mid b$, alors $\operatorname{pgcd}(a,b)=a$. (Le plus petit « absorbe » l'autre.)
Soit $r$ le reste de la division euclidienne de $a$ par $b$. Alors :
On remplace le couple $(a,b)$ par le couple plus petit $(b,r)$ — sans changer le pgcd.
Car $a=bq+r$ : par combinaison linéaire, $a$ et $b$ ont exactement les mêmes diviseurs communs que $b$ et $r$.
On itère le lemme jusqu'au reste $0$. Pour $\operatorname{pgcd}(230,22)$ :
Le dernier reste non nul est $\boxed{2}$, donc $\operatorname{pgcd}(230,22)=2$.
def pgcd(a, b): while b != 0: r = a % b a = b b = r return a
Si $d=\operatorname{pgcd}(a,b)$, alors $\operatorname{Div}(a)\cap\operatorname{Div}(b)=\operatorname{Div}(d)$ : tout diviseur commun divise le pgcd.
$\operatorname{pgcd}(ka,kb)=k\times\operatorname{pgcd}(a,b)$ pour $k\in\mathbb{N}^*$ (et $|k|$ dans $\mathbb{Z}$).
Si $d=\operatorname{pgcd}(a,b)$, on peut écrire $a=da'$ et $b=db'$ avec $a'$ et $b'$ premiers entre eux.
$a$ et $b$ sont premiers entre eux lorsque $\operatorname{pgcd}(a,b)=1$, c'est-à-dire $\operatorname{Div}(a)\cap\operatorname{Div}(b)=\{-1,1\}$.
$a$ et $b$ sont premiers entre eux si, et seulement si :
Plus généralement, $d=\operatorname{pgcd}(a,b)$ équivaut à : $d\mid a$, $d\mid b$ et $\exists(u,v),\ au+bv=d$.
Le couple $(u,v)$ n'est pas unique : pour $5$ et $3$, $(-1,2)$ et $(2,-3)$ conviennent tous deux.
Pour $\operatorname{pgcd}(44064,2975)=17$, la remontée donne :
Si une solution est évidente (petits nombres), inutile de remonter : on la lit directement.
L'hypothèse « premiers entre eux » est indispensable : $6\mid(-8)\times 75$ mais $6\nmid 75$ (car $6\wedge 8=2$).
Si $a\mid n$, $b\mid n$ et $a\wedge b=1$, alors $ab\mid n$. (Ex. $2\mid n$ et $3\mid n$ premiers entre eux $\Rightarrow 6\mid n$.)
$\operatorname{pgcd}(114,30)=6$ divise $54$ ✓. Solution évidente $(1,-2)$, d'où $S=\{(1+5k,\ -2-19k)\mid k\in\mathbb{Z}\}$.
Si $a\wedge n=1$, alors $a$ est inversible modulo $n$ : l'équation a une unique classe de solutions, $x\equiv x_0\ [n]$.
$3x\equiv 1\ [5]$ : $3\wedge 5=1$ et $x_0=2$ convient (car $3\times 2=6\equiv 1$). Donc $S=\{x\mid x\equiv 2\ [5]\}$ : $2$ est l'inverse de $3$ modulo $5$.