Lemme chinois - petite question

il y a de fortes chances.

Bonsoir,

Tu poses toutes les divisions en lignes (ou dans un tableau) et tu les "remontes" une à une en réinjectant l'expression des restes successifs en fonction des dividendes, diviseurs et quotients précédents (r = a - b*q).

Sur un exemple : avec 25 et 16.
\begin{tabular}{rrrrrr}
&a& b& q& r \\
&25& 16& 1& 9& [1° étape] \\
&16& 9 &1 &7 &[2° étape] \\
&9& 7 &1 &2 &[3° étape] \\
&7& 2 &3 &1 &[4° étape]
\end{tabular} \begin{align*}
1 &= 7 - 2*3 \\
1 &= (16 - 9*1) - (9 - 7*1)*3 \\
1 &= (16 - (25 - 16*1)*1) - ((25 - 16*1) - (16 - 9*1))*3 \\
1 &= (16 - (25 - 16*1)*1) - ((25 - 16*1) - (16 - (25 - 16*1)*1))*3
\end{align*} Quand on a plus qu'une combinaison linéaire des deux nombres choisis on simplifie proprement :
\begin{align*}
1 &= (2*16 - 25) - (25 - 16 - (16*2 - 25))*3 \\
1 &= (2*16 - 25) - (2*25 - 3*16)*3 \\
1 &= 11*16 - 7*25
\end{align*} Et voilà.

Mais il y a peut-être plus rapide ?

De rien, et je ne pense pas me tromper en te disant que tous les "réguliers" du forum sont prêts à t'aider en cas de besoin.

Au passage : quel est ce tableau que tu fais ? Les calculs effectués avec ta méthode sont-ils plus rapides ? Je suis intéressé si c'est le cas.

Il existe d'autres méthodes pour déterminer {\it des} coefficients de Bézout $au+bv=1$ (qui ne sont pas uniques, bien entendu). L'algorithme d'Euclide est la plus connue, puisqu'elle est implémentée dans les machines, mais on peut aussi travailler via les congruences $\mod a$ et $\mod b$. Mais le problème est d'une difficulté similaire, puisqu'il faut alors déterminer des inverses $\mod a$ et $\mod b$.

{\bf Exemple}. Déterminer des entiers $u,v$ tels que $12u + 7v = 1$.

Avec la méthode évoquée ci-dessus, cette équation implique le système de congruences $5 u \equiv 1 \pmod 7$ et $7v \equiv 1 \pmod {12}$. Puisque $5 \times 3 = 15 = 1 + 2 \times 7$, on obtient $u \equiv 3 \pmod 7$. De même, puisque $7 \times 7 = 49 = 1 + 4 \times 12$, il vient $v \equiv 7 \pmod {12}$. Autrement dit, on a $u = 3 + 7h$ et $v = 7 + 12k$ avec $h,k \in \Z$. Réciproquement, remplacer $u,v$ par ces valeurs dans l'équation de départ fournit : $84h + 84k = - 84$, ou encore $k = -1 - h$.

Conclusion : les entiers $u = 3 + 7h$ et $v = -5 - 12h$, avec $h \in \Z$, fournissent des coefficients demandés. Par exemple, avec $h=0$, $(u,v) = (3,-5)$ convient.

Borde.