Un algorithme de calcul d'un inverse

stfj

Bonjour
Je dispose d'un algorithme de calcul dont je souhaite démontrer la validité.
Pour l'illustrer, je considère l'exemple de la détermination de l'inverse de $\bar8$ dans $\mathbb{Z}/37\mathbb{Z}.$

Au début de son livre, Arithmétique, François Liret utilise l'équivalence $$a=bq+r~\Longleftrightarrow~ \begin{bmatrix} b \\ r \end{bmatrix}=\begin{bmatrix} 0 & 1 \\ {\color{Blue}1} & -q \end{bmatrix}.\begin{bmatrix} a \\ b  \end{bmatrix}.$$Ici,$$\begin{bmatrix} 2 \\ 1 \end{bmatrix}=\begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -4 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix}.$$
On obtient successivement :
\begin{align*}\begin{bmatrix} 2 \\ 1 \end{bmatrix}&=\begin{bmatrix} 1 & -1 \\ {\color{Blue}-1}& 2 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -1 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -4 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix}\\[1mm]
\begin{bmatrix} 2 \\ 1 \end{bmatrix}&=\begin{bmatrix} -1 & 2 \\ {\color{Blue}2} & -3 \end{bmatrix}.\begin{bmatrix} 0 & 1 \\ 1 & -4 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix} \\[1mm]
\begin{bmatrix} 2 \\ 1 \end{bmatrix}&=\begin{bmatrix} 2 & -9 \\ {\color{Blue}-3} & (-3)\times(-4)+2 \end{bmatrix}.\begin{bmatrix} 37 \\ 8 \end{bmatrix}\end{align*}
L'algorithme que je propose consiste simplement à écrire :

37..........8...........5..............3...............2....................1
..............-4..........-1............-1.............-1
................a.........−3...........2...............−1..................1..........0

Sur la première ligne, on écrit d'abord "37..........8........" puis les restes des divisions euclidiennes successives.
Sur la deuxième ligne,  on écrit les quotients des divisions euclidiennes successives.
Puis on écrit les opposés des quotients toujours sur la deuxième ligne (d'où les -).
Enfin, sur la troisième ligne, on commence par la droite en écrivant "1........0" et on complète progressivement vers la gauche en faisant successivement :
(-1)*1+0=-1  
(-1)*(-1)+1=2
(-1)*2+(-1)=-3
et enfin a=(-4)*(-3)+2, qui fournit l'inverse de $\bar8$ dans $\mathbb{Z}/37\mathbb{Z}$.

Je me suis efforcé d'être le plus clair possible ainsi que d'utiliser la couleur bleue de $\rm\LaTeX$ pour commencer à faire le lien entre la méthode exposée par François Liret et l'algorithme exposé. Me reste à achever, avec votre aide j'espère, la démonstration de la validité de l'algorithme.
Cordialement.
________________________
Remarque : j'avais déjà exposé cet algorithme dans un autre post mais comme il était noyé parmi d'autres informations, je me permets de le reposter ici.

stfj

Je me rends compte que cet algorithme permet en outre d'obtenir très aisément les coefficients de Bézout $(u,v)$ tels que $37u+8v=1$, en l'occurrence $37\times(-3)+8\times14=1$. Pour un autre exemple, voir ici.

Positif

Comme tu l'écris, trouver un inverse dans $\mathrm{Z} / p \mathrm{Z} $  c'est déterminer une relation de Bézout. C'est donc en fait l'algo d'Euclide.

stfj

@Positif : bonjour. En effet, il s'agit de l'algorithme d'Euclide étendu, de toute évidence. Ce que je cherche depuis quelques semaines voire quelques mois- en dillettante, il est vrai-, c'est une démonstration du fait que l'algo proposé (sans latex) fournira le même résultat que l'algorithme proposé par François Liret par exemple (avec $\rm\LaTeX$).

stfj

Voici un premier jet de démonstration : quand on analyse l'algorithme de François Liret, on se rend compte que, pour le problème qui nous occupe, seuls importent les coefficients $M_{2,1}$ et $M_{2,2}$ des matrices, autrement dit les coefficients de la deuxième ligne. Quand on calcule progressivement les produits de matrices $2\times2$, que se passe-t-il? $M_{2,2}$ vient prendre la place de $M_{2,1}$ et la nouvelle valeur de $M_{2,2}$ est $M_{2,1}+M_{2,2}\times(-q_i)$ et c'est exactement ce qui se passe dans le cadre de l'algorithme présenté sans latex.

troisqua

Déjà entièrement détaillé :

https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2377677/#Comment_2377677

Si tu veux écrire ça avec des matrices, il faut comprendre que ce n'est qu'une autre présentation de l'algo d'Euclide étendu (en gros on manipule deux lignes de coefficients à chaque étape pour obtenir les deux suivantes). J'avais fait un petit exo où on prouve l'algorithme et où on prouve sa complexité "pire des cas" (en pièce jointe)

stfj

@troisqua : bonjour, j'ai parcouru le post d'Oshine et les commentaires, ainsi que tes pièces jointes. Mais je ne trouve nulle part la présentation claire fournie par l'algorithme : 
37..........8...........5..............3...............2....................1
..............-4..........-1............-1.............-1
................a.........−3...........2...............−1..................1..........0
que j'ai expliqué dans mon post. 
Aussi, je ne considère pas que la réponse que j'attends y soit "entièrement détaillée".
Par ailleurs, j'ai parfaitement compris que l'écriture matricielle n'est qu'une autre présentation de l'algorithme d'Euclide, ce qui n'est pas difficile à comprendre.

troisqua

Ce que j'écris dans mon papier revient à écrire
\begin{eqnarray*} a & = & 37\\ b & = & 8\left(q=4\right)\\ a-4b & = & 5\left(q=1\right)\\ -a+5b & = & 3\left(q=1\right)\\ 2a-9b & = & 2\left(q=1\right)\\ -3a+14b & = & 1 \end{eqnarray*} donc l'inverse de $\overline{8}$ dans $\mathbb{Z}/37\mathbb{Z}$ est $\overline{14}$. La présentation matricielle de ce que je viens d'écrire c'est ce que tu écris mais ça n'apporte rien au calcul précédent et ça cache le fonctionnement de l'algorithme (qui consiste juste à diminuer le plus vite possible une combinaison de $a$ et de $b$ pour obtenir la plus petite). Je pense que toute autre méthode ou présentation revient à faire les mêmes calculs mais en plus long... (sauf si on fait la petite variante consistant à autoriser des restes négatifs) qui donnerait : \begin{eqnarray*}a & = & 37\\ b & = & 8\left(q=5\right)\\ a-5b & = & -3\left(q=-3\right)\\ 3a-14b & = & -1 \end{eqnarray*} donc l'inverse de  $\overline{8}$ dans $\mathbb{Z}/37\mathbb{Z}$ est $\overline{14}$. Bref, deux lignes suffisent

stfj

@troisqua : ça a l'air en effet de bien fonctionner . On trouve l'explication dans les pièces jointes ?
un défi : 
1261........23........19..........4..........3........1
.................-54......-1..........-4.........-1
..................a.........-6............5........-1........1.......0
L'inverse de 23 dans Z/1261 est -54. (exemple pris au plus grand des hasards)
ça reste performant ?

troisqua

Tu as fait une (des ?) erreur(s) de calcul.

\begin{eqnarray*}a & = & 1261\\ b & = & 23\left(q=54\right)\\ a-54b & = & 19\left(q=1\right)\\ -a+55b & = & 4\left(q=5\right)\\ 6a-329b & = & -1 \end{eqnarray*} Bref, 3 lignes : l'inverse est 329 (modulo 1261).

C'est exactement le même algorithme que toi, t'en rends-tu compte ? (mis à part que j'autorise des restes négatifs pour descendre le plus vite possible). Dans les pièces jointes, on démontre que l'algorithme donne une relation de Bézout, et on montre sa performance (qu'on majore en fonction du nombre de chiffres de $b$).

stfj

@troisqua : l'inverse de 23 dans Z/1261 n'est pas -54 mais (-54)*(-6)+5=329. Nous sommes ok.
Si les deux algorithmes sont les mêmes, tant mieux; mais je t'avoue qu'avec tes $a$ et tes $b$ et tes $q$ non explicités, je ne m'en rends pas compte. Je lirai à tête reposée tes pièces jointes. En particulier le calcul de performance m'intéresse. merci.

troisqua

stfj : tu veux une relation de Bézout entre $a$ et $b$ strictement positifs donc tu cherches une combinaison $au+bv$ minimale non nulle. Donc tu démarres avec deux combinaisons évidentes : $a=a$ et $b=b$ (les deux premières lignes) puis tu cherches à faire diminuer cette combinaison en cherchant combien de fois tu peux retirer $b$ de $a$ (c'est ça $q$). Tu fais alors première ligne moins $q$ fois la deuxième. Et ainsi de suite (c'est ça que tu fais avec tes matrices 2x2)

stfj

@troisqua : ok, je tiens ton algo grâce l'explication que tu viens de donner.

troisqua

Cool

Al-Kashi

Bonjour stfj

Le sujet a été abordé récemment dans le fil inversibles dans $\Z/n\Z$. Il existe d'autres méthodes pour calculer un inverse modulaire.Par exemple, si tu cherches l'inverse de $8$ modulo $37$, tu peux écrire:

$\overline{8^{-1}}=37\Big(\dfrac{1}{37*8}-\dfrac{1}{8*5}+\dfrac{1}{5*3}-\dfrac{1}{3*2}+\dfrac{1}{2*1}\Big)$.

Comme je l'ai déjà précisé, si tu souhaites programmer cet algorithme et même en pratique, on peut ne pas tenir compte des restes successifs dont le produit est supérieur à $n$.

Une autre méthode applicable ici, car $37$ est un nombre premier: $37=8*4+5=7*5+2=18*2+1$.

Tu obtiens alors $\overline{8^{-1}}=-4*(-7)*(-18)=-504\equiv 14 \mod 37$
Al-Kashi