'Gauss's Algorithm' for computing modular fractions and inverses

Below we compare the related forms. First is the iterated descent $\,a\to 103\bmod a\,$ used by Gauss. Second is that rearranged into the form of descending multiples of $60.\,$ Third is the fractional view, and fourth is the graph of the descending multiples of $60$ (denominator descent graph).

$$\begin{align} 103\bmod{60} &= 103 - 1(60) = 43\\ 103\bmod 43 &= 103\color{#0a0}{-2(43)=17}\\ 103\bmod 17 &= 103-6(17) = 1 \end{align}\qquad\qquad\quad$$

$$\begin{array}{rl} \bmod{103}\!:\qquad\ (-1)60\!\!\!\! &\equiv\, 43 &\Rightarrow\ 1/60\equiv -1/43\\[.3em] \smash[t]{\overset{\large\color{#0a0}{*(-2)}}\Longrightarrow}\ \ \ \ \ \ \ \ \ \ (-2)(-1)60\!\!\!\! &\equiv \color{#0a0}{(-2)43\equiv 17}\!\! &\Rightarrow\ 1/60\equiv\ \ \ 2/17\\[.3em] \smash[t]{\overset{\large *(-6)}\Longrightarrow}\ \ \color{#c00}{(-6)(-2)(-1)}60\!\!\!\! &\equiv (-6)17\equiv 1 &\Rightarrow\ 1/60 \equiv {\color{#c00}{-12}}/1\\ \end{array}$$

$$ \begin{align} &\dfrac{1}{60}\ \,\equiv\ \ \dfrac{-1}{43}\, \ \equiv\, \ \dfrac{2}{17}\, \equiv\, \dfrac{\color{#c00}{-12}}1\ \ \ \rm[Gauss's\ algorithm]\\[.3em] &\, 60\overset{\large *(-1)}\longrightarrow\color{#0a0}{43}\overset{\large\color{#0a0}{*(-2)}}\longrightarrow\,\color{#0a0}{17}\overset{\large *(-6)}\longrightarrow 1\\[.4em] \Rightarrow\ \ &\,60*(-1)\color{#0a0}{*(-2)}*(-6)\equiv 1\ \Rightarrow\ 60^{-1}\rlap{\equiv (-1)(-2)(-6)\equiv \color{#c00}{-12}} \end{align}$$

The translation from the first form (iterated mods) to the second (iterated smaller multiples) is realized by viewing the modular reductions as modular multiplications, e.g.

$$\ 103\color{#0a0}{-2(43) = 17}\,\Rightarrow\, \color{#0a0}{-2(43) \equiv 17}\!\!\pmod{\!103} $$

This leads to the following simple recursive algorithm for computing inverses $\!\bmod p\,$ prime.

$\begin{align}\rm I(a,p)\ :=\ &\rm if\ \ a = 1\ \ then\ \ 1\qquad\qquad\ \ \ ; \ \ a^{-1}\bmod p,\,\ {\rm for}\ \ a,p\in\Bbb N\,\ \ \&\,\ \ 0 < a < p\ prime \\[.5em] &\rm else\ let\ [\,q,\,r\,]\, =\, p \div a\qquad ;\, \ \ p = q a + r\ \Rightarrow \color{#0a0}{-qa\,\equiv\, r}\!\!\pmod{\!p},\ \ 0 < r < a\,\\[.2em] &\rm\ \ \ \ \ \ \ \ \ ({-}q*I(r,p))\bmod p\ \ \ ;\ \ because\ \ \ \dfrac{1}a \equiv \dfrac{-q}{\color{#0a0}{-qa}}\equiv \dfrac{-q}{\color{#0a0}r}\equiv -q * I(r,p)\ \ \ \ \ \color{#90f}{[\![1]\!]} \end{align} $

Theorem $\ \ I(a,p) = a^{-1}\bmod p$

Proof $\ $ Clear if $\,a = 1.\,$ Let $\,a > 1\,$ and suppose for induction the theorem holds true for all $\,n < a$. Since $\,p = qa+r\,$ we must have $\,r > 0\,$ (else $\,r = 0\,\Rightarrow\,a\mid p\,$ and $\,1< a < p,\,$ contra $\,p\,$ prime). Thus $\,0 < r < a\,$ so induction $\,\Rightarrow\,I(r,p)\equiv \color{#0a0}{r^{-1}}$ so reducing equation $\color{#90f}{[\![1]\!]}\bmod p\,$ yields the claim.