Identité de Bézout
Fondamental :
Soit \(a\) et \(b\) deux entiers naturels non nuls et \(d=PGCD(a, b)\).
Alors il existe deux entiers relatifs \(u\) et \(v\) tels que : \(au + bv = d\).
Exemple :
\(PGCD(35, 55)=5\). On a \(2\times 55 -3\times 35 = 5\)
Remarque :
Ce couple \((u, v)\) n'est pas unique. En effet :
\(2\times 55 -3\times 35 = 5\)
\(9\times 55 -14\times 35 = 5\)
\(16\times 55 -25\times 35 = 5\)
\(23\times 55 -36\times 35 = 5\)
\(30\times 55 -47\times 35 = 5\)
etc... Saurez-vous en trouver d'autres ?
Attention : La réciproque est fausse
\(55\times 8 - 35 \times 7 = 195\) et bien évidemment, 195 n'est pas le PGCD de 55 et 35 !
Démonstration au programme
Fondamental : Résultat préliminaire (admis)
Nous admettrons cette propriété fondamentale de l'ensemble \(\mathbb N\) des entiers naturels :
Toute partie non vide de \(\mathbb N\) possède un plus petit élément.
On appelle E l'ensemble des entiers strictement positifs de la forme \(am + bn\) avec \(m, n \in \mathbb Z\)
\(a \in E\) donc \(E\) est non vide. Il contient par conséquent un plus petit élément \(d\) strictement positif. \(d\in E\) donc \(d=au+bv\) avec \(u, v\in\mathbb Z\)
Nous allons démontrer que \(d = PGCD(a ; b)\). Pour cela, nous procéderons en deux étapes
PGCD(a ; b) ≤ d
\(PGCD(a ; b)\) divise \(a\) et \(b\) donc divise toute combinaison linéaire de \(a\) et \(b\).
\(d\) est de la forme \(am + bn\) et donc \(PGCD(a ; b)\) divise \(d\).
On en conclut que \(PGCD(a ; b) \leqslant d\)
d ≤ PGCD(a ; b)
On effectue la division euclidienne de \(a\) par \(d\) : \(a = dq + r\) avec \(0 \leqslant r < d\)
On a donc \(r = a − dq = a − (au + bv)q = a − auq − bvq = (1 − uq)a − vqb\)
Or \(r\) est donc un entier positif ou nul.
Supposons que \(r>0\), alors \(r\in E\), ce qui est impossible car \(r<d\) et \(d\) est le plus petit élément de E
Donc \(r = 0\), ce qui signifie que \(d\) divise \(a\).
La même démonstration s'applique pour dire que \(d\) divise \(b\). \(d\) est un diviseur commun à \(a\) et \(b\), il est donc inférieur ou égal au plus grand diviseur commun de \(a\) et \(b\).
On conclut donc que \(d=PGCD(a ;b)\) et donc \(PGCD(a ;b)=au+bv\)
Remarque :
L'identité de Bézout nous dit qu'il existe deux entiers \(u\) et \(v\) mais ne nous donne aucun moyen en pratique de les déterminer ! La preuve ne nous éclaire pas plus sur ce point.
Nous allons appeler l'algorithme d'Euclide à la rescousse afin de déterminer ces deux entiers.