# Solving linear congruences and multiplicative inverses

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?

• The answer you linked says that modular fraction arithmetic is valid for fractions with denominator coprime to the modulus. – J. W. Tanner Jul 23 at 13:36
• Oh yes, in fact it is the same now. I recall that he always referred to this only when modulus was prime. Like here math.stackexchange.com/questions/2991/… – Michael Munta Jul 23 at 13:56
• e.g. try computing $\,7^{-1}\bmod 30\$ by Gauss's algorithm to see the problems that arise. – Bill Dubuque Jul 23 at 14:06
• math.stackexchange.com/questions/257127/… – lab bhattacharjee Jul 23 at 14:35
• @lab How is the link you gave supposed to be related to the specific algorithm being discussed here? It seems there is no relation at all (other than being a different method to compute modular inverses). – Bill Dubuque Jul 23 at 16:52