Coefficients de Bézout pour 3 nombres

Une solution possible est d’utiliser deux fois l’algorithme classique pour deux polynômes, mais il existe sûrement une méthode plus efficace.

Supposons $a\geqslant b\geqslant c\geqslant 0$. Soit $d$ le PGCD. Pour trouver un triplet $(u,v,w)$ tel que $au+bv+cw=d$, on peut généraliser l'algorithme d'Euclide étendu. On pose $a_1=a$, $a_2=b$, $a_3=c$, $X_1=(1,0,0)$, $X_2=(0,1,0)$, $X_3=(0,0,1)$.

Pour tout $k$ :

Tant que $a_k>0$ et $a_k$ ne divise pas $a_{k-2}$ on fait la division Euclidienne $a_{k-2}=q_{k+1}a_k+a_{k+1}$ et on pose $X_{k+1}=X_{k-2}-q_{k+1}X_k$.

Ensuite, tant que $a_k>0$, on fait la division Euclidienne $a_{k-1}=q_{k+1}a_k+a_{k+1}$ et on pose $X_{k+1}=X_{k-1}-q_{k+1}X_k$.

L'algorithme s'arrête lorsqu'on tombe sur $a_{k+1}=0$. On pose alors $(u,v,w)=X_k$.

Exemple : $(a,b,c)=(15,10,6)$. On a $a_4=3$, $q_4=2$, $X_4=(1,0,-2)$, $a_5=1$, $q_5=3$, $X_5=(-3,1,6)$, $a_6=0$. Le PGCD vaut $1$, et le triplet $(u,v,w)=(-3,1,6)$ convient.