Curious about an old algorithm which calculates modular inverse I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic

Background: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3). I just read the abstract and algorithm itself, I don't understand Chinese. It offers new method to find a Modular inverses. It has some interesting properties that I observed:


during each step iteration of the loop: $x_{11} * x_{22} + x_{12} * x_{21} = m$ which is good to validate the result during each iteration
algorithm terminates in even number of steps for some unknown reason


In abstract section, author says this method was invented by this mathematicians.

My question is, why does this algorithm always terminate in aeven number of steps (or number of iterations of the loop is always even)?

Algorithm to calculate: $a^{-1} (\bmod m)$:


  $\text{xgcd}(a, m):$
  
  $\quad x_{11} \leftarrow 1, x_{21} \leftarrow 0, x_{12} \leftarrow a, x_{22} \leftarrow m$
  
  $\quad \text{While }(x_{12} &gt; 1) \text{ do}$
  
  $\quad \quad \text{If }(x_{22} &gt; x_{12}) \text{ then}$
  
  $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{22} - 1}{x_{12}}\Big\rfloor$
  
  $\quad\quad\quad\quad r \leftarrow x_{22} - q ~x_{12}$
  
  $\quad\quad\quad\quad \begin{pmatrix}x_{11} &amp; x_{12}\\x_{21} &amp; x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}x_{11} &amp; x_{12}\\q~x_{11} + x_{21} &amp; r\end{pmatrix} $ 
  
  $\quad\quad \text{If }(x_{12} &gt; x_{22}) \text{ then}$ 
  
  $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{12} - 1}{x_{22}}\Big\rfloor$ 
  
  $\quad\quad\quad\quad r \leftarrow x_{12} - q~x_{22}$
  
  $\quad\quad\quad\quad \begin{pmatrix}x_{11} &amp; x_{12}\\x_{21} &amp; x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}q~x_{21} + x_{11} &amp; r\\x_{21} &amp; x_{22}\end{pmatrix}$
  
  $\quad \text{Return } x_{11}$



Screenshot of the algorithm
Python and SageMath implementations
You can replace:

$$ ~~q \leftarrow \Big\lfloor\frac{a - 1}{b}\Big\rfloor $$
$$ r \leftarrow a - q ~b  $$

By $q, r \leftarrow \text{divmod}(a, ~ b)$


  Algorithm terminates in even number of steps for some unknown reason


Those matrices assignments seem to be a fancy way of writing:

$$ \gcd(m_0, \color{blue}{a_0}) = \gcd(a_0, \color{red}{m_0 \pmod{a_0}}) = \gcd(\color{red}{m_1}, \color{blue}{\underbrace{a_0 \pmod{m_1}}_{a_1}}) = \dots = \gcd(m_n, 1)$$

So $a_i$ decreases every $2$ iterations, and $\gcd$ stops when $a_n = 1$.

Of course, you're not interested in computing the $\gcd$ per see, since you already know it's $1$, but finding the integers such that $Xm + Ya = gcd(m, a) = 1$.