1

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?

Bernard
  • 173,269
  • 10
  • 66
  • 166
Michael Munta
  • 125
  • 6
  • 21
  • The answer you linked says that modular fraction arithmetic is valid for fractions with denominator coprime to the modulus. – J. W. Tanner Jul 23 '19 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 https://math.stackexchange.com/questions/2991/not-understanding-simple-modulus-congruency/3230#3230 – Michael Munta Jul 23 '19 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 '19 at 14:06
  • https://math.stackexchange.com/questions/257127/how-to-convert-a-diophantine-equation-into-parametric-form – lab bhattacharjee Jul 23 '19 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 '19 at 16:52
  • @Bill well it is still possible, it just makes it not as efficient. Multiply by $17$, reduce, multiply by $-31$, reduce. Inverse is $-3689 \equiv 13$ (mod $30$) – Michael Munta Jul 23 '19 at 19:09
  • Since an inverse exists it is always possible to find it (e.g. by brute force search). But the point is that the *efficient descent process* used in Gauss's algorithm doesn't work in general for composite moduli. Instead we can employ more general efficient algorithms, e.g. the [fractional extended Euclidean algorithm](https://math.stackexchange.com/a/2054339/242), but that's a bit more complex (using *multi-valued* modular fractions). If you are first learning these ideas then it's better to work with the equations vs. such generalized fractions (compare the two in the prior-linked post) – Bill Dubuque Jul 23 '19 at 19:17

0 Answers0