Coefficients de Bézout

Publié le 13/02/17

Soient {m,n} dans {\mathbb{N}} (non tous les deux nuls).
Alors il existe une infinité de {(u,v)\in\mathbb{Z}^2} tel que {um+vn=m\wedge n}.
On dit que {u} et {v} sont des coefficients de Bézout de {m} et {n}.

L’algorithme d’Euclide appliqué à {(m,n)} fournit un couple {(u,v)} « minimal ».

On va écrire deux fonctions Python de calcul des entiers u,v,u\wedge d.

1. Une fonction Python récursive

Si {n=0}, une solution de {um+vn=m\wedge n=m} est {(u=1,v=0)}.

Si n\ge0, soit {m=nq+r} (avec {0\le r\lt n}) la division euclidienne de {m} par {n}.

Soit {(u',v')} un couple vérifiant {u'n+v'r=n\wedge r}. Alors:

{\begin{array}{rl}m\wedge n&=n\wedge r=u'n+v'(m-nq)\\&=v'm+(u'-qv')n\end{array}}Le couple {(u=v',v=u'-qv')} vérifie donc {um+vn=m\wedge n}.

On en déduit une fonction récursive utilisant cette idée.

La fonction bezoutr reçoit les entiers positifs {m,n}, et renvoie dans un triplet {(u,v,u\wedge v)} les coefficients {u,v} tels que {um+vn=u\wedge v}.

Exemple: avec {\begin{cases}m=14938\\n=9471\end{cases}}, on constate que {\begin{cases}m\wedge n=77\\26m-41n=77\end{cases}}

2. Une fonction Python itérative

On Considère les équations {(E_\delta): am+bn=\delta}, d’inconnue {(a,b)} dans {\mathbb{Z}^2}.
On note que {(1,0)} vérifie {(E_m)}, et que {(0,1)} vérifie {(E_n)}.

Soit {\alpha=q\beta+r} la division euclidienne d’un entier {\alpha} par un entier {\beta}.
Il est alors facile de passer d’une solution {(E_\alpha)} et de {(E_\beta)} à une solution de {(E_r)}.

Ces remarques conduisent à une fonction itérative.
On utilise pour cela un tableau Numpy C de deux lignes et trois colonnes.
Au début {C[0]=[1,0,m]} (pour {(E_m)}) et {C[1]=[0,1,n]} (pour {(E_n)}).

On procède à des divisions successives sur les seconds membres, jusqu’à un reste nul.
À chaque pas, on trouve une ligne {[u,v,\delta]}, où {\delta} est l’un des restes successifs.
Il faut bien sûr actualiser le tableau {C} à chaque étape.

À la fin, la solution {[u,v,m\wedge n]} est dans {C[0]}.

On reprend l’exemple utilisé précédemment.