Curious about an old algorithm which calculates modular inverse
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$.