Entiers premiers entre eux, théorème de Bézout~3 min
$a$ et $b$ sont premiers entre eux lorsque $\mathrm{pgcd}(a,b)=1$ : leur seul diviseur commun positif est $1$.
Forme irréductible : si $d=\mathrm{pgcd}(a,b)$, alors $a=da'$ et $b=db'$ avec $a'\wedge b'=1$ (car $\mathrm{pgcd}(da',db')=d\,\mathrm{pgcd}(a',b')$).
Soit $a,b$ des entiers non tous deux nuls, $d=\mathrm{pgcd}(a,b)$.
• Identité de Bézout : il existe $(u,v)\in\mathbb{Z}^2$ tel que $\boldsymbol{au+bv=d}$. (Le couple n'est pas unique.)
• Théorème de Bézout : $a\wedge b=1\iff$ il existe $(u,v)\in\mathbb{Z}^2$ tel que $au+bv=1$.
Soit $E=\{au+bv\ ;\ (u,v)\in\mathbb{Z}^2\ \text{et}\ au+bv\gt 0\}$. $E$ est une partie de $\mathbb{N}^\ast$, non vide (elle contient $|a|$ ou $|b|$, l'un des deux étant non nul) : elle admet un plus petit élément $d_0=au_0+bv_0$. Montrons que $d_0=\mathrm{pgcd}(a,b)$.
$d_0$ divise $a$. Division euclidienne de $a$ par $d_0$ : $a=d_0q+r$ avec $0\leq r\lt d_0$. Alors $r=a-d_0q=a-(au_0+bv_0)q=a(1-u_0q)+b(-v_0q)$ est une combinaison linéaire de $a$ et $b$. Si $r\gt 0$, alors $r\in E$ et $r\lt d_0$ : contradiction avec la minimalité de $d_0$. Donc $r=0$ et $d_0\mid a$. De même $d_0\mid b$.
$d_0$ est le plus grand. Soit $\delta$ un diviseur commun à $a$ et $b$ : $\delta$ divise $au_0+bv_0=d_0$, donc $\delta\leq d_0$.
Ainsi $d_0$ est le pgcd de $a$ et $b$, et $au_0+bv_0=\mathrm{pgcd}(a,b)$.
Au passage : tout diviseur commun à $a$ et $b$ divise leur pgcd. Autre preuve possible : en « remontant » l'algorithme d'Euclide, chaque reste est une combinaison linéaire de $a$ et $b$ (voir ci-dessous).
($\Rightarrow$) C'est l'identité de Bézout avec $d=1$. ($\Leftarrow$) Si $au+bv=1$, tout diviseur commun $\delta$ à $a$ et $b$ divise $au+bv=1$, donc $\delta=\pm1$ : $\mathrm{pgcd}(a,b)=1$.
1. Écrire les divisions d'Euclide, puis exprimer chaque reste : $r=a-bq$.
2. Partir de l'avant-dernière ligne ($d=\dots$) et remplacer les restes du plus récent au plus ancien, en gardant $a$ et $b$ comme des « lettres » (ne pas effectuer les produits $2\times735$, etc.).
3. Vérifier le résultat par un calcul direct.
Avec $1848$ et $735$ (divisions successives de l'algorithme d'Euclide) : $378=1848-2\times735$, $357=735-378$, $21=378-357$. $$\begin{aligned}21&=378-357=378-(735-378)=2\times378-735\\ &=2\times(1848-2\times735)-735=2\times1848-5\times735.\end{aligned}$$ Vérification : $3696-3675=21$. $(u,v)=(2,-5)$.
def bezout(a, b):
# renvoie (d, u, v) : a*u + b*v = d
if b == 0:
return a, 1, 0
d, u, v = bezout(b, a % b)
return d, v, u - (a // b) * v
bezout(1848, 735) renvoie (21, 2, -5). Idée : si $bu+rv=d$ avec $r=a-bq$, alors $av+b(u-qv)=d$.