elementary number theory - How to find the inverse modulo m?

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

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

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

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

Thanks,

Answer

1. One method is simply the Euclidean algorithm:
   $$\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)$. Viewing the equation $1 = 9(7) -2(31)$ modulo $31$ gives $1 \equiv 9(7)\pmod{31}$, so the multiplicative inverse of $7$ modulo $31$ is $9$. This works in any situation where you want to find the multiplicative inverse of $a$ modulo $m$, provided of course that such a thing exists (i.e., $\gcd(a,m) = 1$). The Euclidean Algorithm gives you a constructive way of finding $r$ and $s$ such that $ar+ms = \gcd(a,m)$, but if you manage to find $r$ and $s$ some other way, that will do it too. As soon as you have $ar+ms=1$, that means that $r$ is the modular inverse of $a$ modulo $m$, since the equation immediately yields $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}.$$
   Here, you reduce modulo $31$ 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 $31$ 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 $5$ because that's the smallest multiple of $7$ that is larger than $32$, and later I multiplied by $8$ because it was the smallest multiple of $4$ that is larger than $32$. 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},$$
namely, it has solutions if and only if $\gcd(a,m)|b$, in which case it has exactly $\gcd(a,m)$ solutions modulo $m$.

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

Once you know how to solve them in the case where $\gcd(a,m)=1$, you can take the general case of $\gcd(a,m) = d$, and from

$$ax\equiv b\pmod{m}$$
go to
$$\frac{a}{d}x \equiv \frac{b}{d}\pmod{\frac{m}{d}},$$
to get the unique solution $\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}.$$