Lemme chinois - petite question
dans Arithmétique
Bonjour,
J'ai compris le principe du lemme chinois mais je ne connais pas la méthode pour déterminer u, v tels que au + bv = 1 (évidemment a et b sont premiers entre eux) ...
Serait-ce par l'algorithme d'Euclide étendu ?
Merci d'avance de vos réponses
@++
J'ai compris le principe du lemme chinois mais je ne connais pas la méthode pour déterminer u, v tels que au + bv = 1 (évidemment a et b sont premiers entre eux) ...
Serait-ce par l'algorithme d'Euclide étendu ?
Merci d'avance de vos réponses
@++
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
@+
[Euclide mérite bien une majuscule AD]
Effectivement et vous méritez mes plus plates excuses!:)-D
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 ?
encore merci et @+
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.
@+
{\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.
> 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.
En fait la méthode est la suivante on cherche à trouver $x, y$ tels que $ax+by=c$
$$\begin{array}{llllll}
&k & r_k & q_k & x_k & y_k \\
&1 & a & * & 1 & 0 \\
&2 & b & q_2 & 0 & 1 \\
&3 & r_3 & .. & .. & .. \\
&... \\
&N-1& r_{N-1}& q_{N-1}& x_{N-1}& y_{N-1} \\
&N & r_N & q_N & x_N & y_N \\
&N+1& r_{N+1}& * & x_{N+1}& y_{N+1}
\end{array}$$
--> $a = b .q_2 + r_3$
--> Les coefficients $q_k, r_k$ sont les coefficients des divisions eculidiennes successives
--> $r_{N+1}=0$
--> $x_1=1 / x_2=0 / y_1=0 / y_2=1$
--> Si $k>2, x(k+1)=x(k-1)-q(k)x(k)$ et $y(k+1)=y(k-1)-q(k)y(k)$
on trouve $x$ et $y$ au rang $N$, pour moi ma méthode est moins rapide que la tienne ... En espérant que tu aies compris ce que j'ai marqué !
@++