Un algorithme de calcul d'un inverse

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.