Inspired by Bill Dubuque's Gauss Algorithm I have been interested in finding such optimal ways of solving simple linear congruences and finding multiplicative inverses.
Bill presented the algorithm for finding a multiplicative inverse modulo $p$ prime. The context is present in the linked answer. I am thinking why is this prime modulus required for such computations. The only requirement is that the number with the coefficient $x$ is coprime to the modulus. Let me give an example:
Suppose $p$ is not prime and we are trying to find a multiplicative inverse of $5$ modulo $8$
$$5x \equiv 1 \pmod 8 $$
What we can do very similarly to Bill's algorithm is multiply both sides by a number coprime to the modulus. Number must be coprime so that the resulting congruence will keep the coefficient of $x$ coprime to the modulus and congruence will have a solution.
We can multiply this by $5$, since $\gcd(5, 8) = 1$.
$$25x \equiv 5 \pmod 8$$
Now we can reduce $25$ modulo $8$ because of the congruence property like so:
$$x \equiv 5 \pmod 8$$
And we have our inverse $x \equiv 5$.
This is a simple example, but I tried doing some other congruences and it worked. Important is to make sure that we multiply by a number coprime to modulus and that after reducing the resulting product modulo we get a lesser number than we started with.
I am new to number theory and this might just be something very obvious, but I wanted to present it here just in case. Can anyone provide some kind of feedback on this?