D'après le théorème de Bachet, si deux entiers relatifs a et b sont donnés et d est leur plus grand diviseur commun (ou pgcd), il existe deux entiers relatifs u et v tels que au + bv = d. Ce théorème se généralise aux polynômes car leur ensemble est également muni d'une division euclidienne. L'idée pour le démontrer est de considérer l'ensemble des polynômes de la forme A U + B V et, plus précisément, son élément de degré minimal, dont on démontre qu'il s'agit du pgcd de A et B (voir l'encadré). Cette démonstration débouche sur un algorithme de calcul consistant, à partir d'un polynôme de la forme A U + B V, à en déduire un autre, de degré inférieur, et à recommencer tant que cela est possible.
Prenons un exemple pour décrire l'algorithme d'Euclide permettant de déterminer un couple (U, V) tel que le degré de U soit strictement inférieur à celui de B, et le degré de V strictement inférieur à celui de A. Soit *A = 3X3 + 2X2 + 2 et B = X2 – 2. En divisant A par B, on obtient : A – B (3X + 2) = 6X + 6 puis, en divisant B par X + 1 : B = (X + 1)(X – 1) – 1*. On en déduit la relation de Bézout suivante :
On en tire que le pgcd de A et B est égal à 1, c'est-à-dire que A et B sont premiers entre eux.
