# How to find the inverse modulo mm?

For example:
$$7x \equiv 1 \pmod{31} 7x \equiv 1 \pmod{31}$$
In this example, the modular inverse of $$77$$ with respect to $$3131$$ is $$99$$. How can we find out that $$99$$? What are the steps that I need to do?

Update
If I have a general modulo equation:
$$5x + 1 \equiv 2 \pmod{6}5x + 1 \equiv 2 \pmod{6}$$

What is the fastest way to solve it? My initial thought was:
$$5x + 1 \equiv 2 \pmod{6}5x + 1 \equiv 2 \pmod{6}$$
$$\Leftrightarrow 5x + 1 – 1\equiv 2 – 1 \pmod{6}\Leftrightarrow 5x + 1 - 1\equiv 2 - 1 \pmod{6}$$
$$\Leftrightarrow 5x \equiv 1 \pmod{6}\Leftrightarrow 5x \equiv 1 \pmod{6}$$

Then solve for the inverse of $$55$$ modulo 6. Is it a right approach?

Thanks.

1. One method is simply the Euclidean algorithm:
\begin{align*} 31 &= 4(7) + 3\\\ 7 &= 2(3) + 1. \end{align*}\begin{align*} 31 &= 4(7) + 3\\\ 7 &= 2(3) + 1. \end{align*}
So $$1 = 7 – 2(3) = 7 – 2(31 – 4(7)) = 9(7) – 2(31) 1 = 7 - 2(3) = 7 - 2(31 - 4(7)) = 9(7) - 2(31)$$. Viewing the equation $$1 = 9(7) -2(31)1 = 9(7) -2(31)$$ modulo $$3131$$ gives $$1 \equiv 9(7)\pmod{31} 1 \equiv 9(7)\pmod{31}$$, so the multiplicative inverse of $$77$$ modulo $$3131$$ is $$99$$. This works in any situation where you want to find the multiplicative inverse of $$aa$$ modulo $$mm$$, provided of course that such a thing exists (i.e., $$\gcd(a,m) = 1\gcd(a,m) = 1$$). The Euclidean Algorithm gives you a constructive way of finding $$rr$$ and $$ss$$ such that $$ar+ms = \gcd(a,m)ar+ms = \gcd(a,m)$$, but if you manage to find $$rr$$ and $$ss$$ some other way, that will do it too. As soon as you have $$ar+ms=1ar+ms=1$$, that means that $$rr$$ is the modular inverse of $$aa$$ modulo $$mm$$, since the equation immediately yields $$ar\equiv 1 \pmod{m}ar\equiv 1 \pmod{m}$$.

2. Another method is to play with fractions Gauss’s method:
$$\frac{1}{7} = \frac{1\times 5}{7\times 5} = \frac{5}{35} = \frac{5}{4} = \frac{5\times 8}{4\times 8} = \frac{40}{32} = \frac{9}{1}.\frac{1}{7} = \frac{1\times 5}{7\times 5} = \frac{5}{35} = \frac{5}{4} = \frac{5\times 8}{4\times 8} = \frac{40}{32} = \frac{9}{1}.$$
Here, you reduce modulo $$3131$$ where appropriate, and the only thing to be careful of is that you should only multiply and divide by things relatively prime to the modulus. Here, since $$3131$$ is prime, this is easy. At each step, I just multiplied by the smallest number that would yield a reduction; so first I multiplied by $$55$$ because that’s the smallest multiple of $$77$$ that is larger than $$3232$$, and later I multiplied by $$88$$ because it was the smallest multiple of $$44$$ that is larger than $$3232$$. Added: As Bill notes, the method may fail for composite moduli.

Both of the above methods work for general modulus, not just for a prime modulus (though Method 2 may fail in that situation); of course, you can only find multiplicative inverses if the number is relatively prime to the modulus.

Update. Yes, your method for general linear congruences is the standard one. We have a very straightforward method for solving congruences of the form $$ax \equiv b\pmod{m},ax \equiv b\pmod{m},$$
namely, it has solutions if and only if $$\gcd(a,m)|b\gcd(a,m)|b$$, in which case it has exactly $$\gcd(a,m)\gcd(a,m)$$ solutions modulo $$mm$$.

To solve such equations, you first consider the case with $$\gcd(a,m)=1\gcd(a,m)=1$$, in which case $$ax\equiv b\pmod{m}ax\equiv b\pmod{m}$$ is solved either by finding the multiplicative inverse of $$aa$$ modulo $$mm$$, or as I did in method $$22$$ above looking at $$\frac{b}{a}\frac{b}{a}$$.

Once you know how to solve them in the case where $$\gcd(a,m)=1\gcd(a,m)=1$$, you can take the general case of $$\gcd(a,m) = d\gcd(a,m) = d$$, and from
$$ax\equiv b\pmod{m}ax\equiv b\pmod{m}$$
go to
$$\frac{a}{d}x \equiv \frac{b}{d}\pmod{\frac{m}{d}},\frac{a}{d}x \equiv \frac{b}{d}\pmod{\frac{m}{d}},$$
to get the unique solution $$\mathbf{x}_0\mathbf{x}_0$$. Once you have that unique solution, you get all solutions to the original congruence by considering
$$\mathbf{x}_0,\quad \mathbf{x}_0 + \frac{m}{d},\quad \mathbf{x}_0 + \frac{2m}{d},\quad\ldots, \mathbf{x}_0 + \frac{(d-1)m}{d}.\mathbf{x}_0,\quad \mathbf{x}_0 + \frac{m}{d},\quad \mathbf{x}_0 + \frac{2m}{d},\quad\ldots, \mathbf{x}_0 + \frac{(d-1)m}{d}.$$