Does modulus m need to be prime in finding the modular inverse? [duplicate]

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.

I'm not sure I've properly understood what you're looking for, but since the reason why the algorithm works seems to me to be patently clear from the formal proof that it does, in fact, work, here's such a proof for the general case.

Starting with a prime $\ p\ $, and an integer $\ b_0\in \left[1, p\right]\ $, the algorithm successively produces integers $\ b_1<b_0,b_2<b_1, \dots, b_{i+1} < b_i, \dots\ $, with $\ b_{i+1} \equiv -q_i\ b_i\ \left(\,\mathrm{mod }\ p\,\right)\ $, until it obtains $\ b_n = 1\ $. As long as $\ b_i \not\in\left\{0, 1\right\}\ $, it's always possible to carry out the next step of the procedure by using the division algorithm: $\ p = q_i\,b_i + b_{i+1}\ $, and since the sequence $\ b_0, b_1, \dots\ b_i, \dots $ is strictly decreasing, the algorithm must eventually terminate with $\ b_n\in\left\{0, 1\right\}\ $. If $\ b_n\ $ were $\ 0\ $, however, the final step of the algorithm would have been $\ p = q_{n-1}\,b_{n-1} + b_n = q_{n-1}\,b_{n-1}\ $, whence $\ b_{n-1}\ $, strictly smaller than the prime $\ p\ $, would be a divisor of it, and hence equal to $\ 1\ $. Thus, the algorithm would have terminated on the preceeding step.

Thus the algorithm always terminates with $\ b_n=1\ $, and we then have \begin{eqnarray} 1&\equiv& -q_{n-1}\,b_{n-1}\equiv q_{n-1}\,q_{n-2}\,b_{n-2}\equiv\dots\\ &\equiv& \left(-1\right)^n\,q_{n-1}\,q_{n-2}\dots q_0\,b_0\ \left(\,\mathrm{mod}\,p\,\right)\ \end{eqnarray}.