1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ The answer you linked says that modular fraction arithmetic is valid for fractions with denominator coprime to the modulus. $\endgroup$ – J. W. Tanner Jul 23 at 13:36
  • $\begingroup$ 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/… $\endgroup$ – Michael Munta Jul 23 at 13:56
  • $\begingroup$ e.g. try computing $\,7^{-1}\bmod 30\ $ by Gauss's algorithm to see the problems that arise. $\endgroup$ – Bill Dubuque Jul 23 at 14:06
  • $\begingroup$ math.stackexchange.com/questions/257127/… $\endgroup$ – lab bhattacharjee Jul 23 at 14:35
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Jul 23 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.