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.

Solution 1:

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}.$$

Solution 2:

We know that $(7,31) = 1$. So you can use the extended Euclidean algorithm. In particular, you can find two integers $s,t$ such that $7s+31t = 1$. So $7s \equiv 1 \pmod {31}$.

Solution 3:

A hint: Try to use Fermats Little theorem:

$a^{p-1}=1 \mod p$ for $p$ prime, and all $a\in \mathbb{Z}$.

Solution 4:

We can visualize the solution to $7x \equiv 1 \pmod{31}$ as the intersection of the two "lines"

$\ \ \ \ \ y \equiv 7x \pmod{31}$ and $y \equiv 1 \pmod{31}$.

The first line is closed under addition and subtraction, since it passes through the origin. If $(x_1, y_1)$ and $(x_2, y_2)$ are points on the line $y \equiv 7x \pmod{31}$, then so are $(x_1+x_2, y_1+y_2)$ and $(x_1-x_2, y_1-y_2)$.

To find a point where the lines intersect, we start with the two points $(1, 7)$ and $(0,31)$ on the first line, and repeatedly subtract one point from another until the $y$-coordinate is 1.

$\ \ \ \ \ (0,31) - (1,7) = (-1, 24)$

$\ \ \ \ \ (-1, 24) - (1,7) = (-2, 17)$

$\ \ \ \ \ (-2, 17) - (1, 7) = (-3, 10)$

$\ \ \ \ \ (-3, 10) - (1, 7) = (-4, 3)$

$\ \ \ \ \ (1,7) - (-4, 3) = (5, 4)$

$\ \ \ \ \ (5,4) - (-4, 3) = (9,1)$

Therefore, $x \equiv 9 \pmod{31}$.

You can speed up this procedure by subtracting a multiple of one point from another point instead. This leads to the Euclidean algorithm.

Solution 5:

There are many methods available, e.g. the extended Euclidean algorithm, $ $ or a special case of Euclid's algorithm that computes inverses modulo primes that I call Gauss's algorithm. $ $ The calculations are usually simpler using modular fraction arithmetic e.g. see here, and here and here for circa $20$ motley worked examples via a handful of methods (and see the sidebar "Linked" questions lists there for many more).

Update $ $ March $16, 2020\!:\,$ for completeness we apply some of the linked methods below.

$\!\!\bmod 31\!:\,\ \dfrac{1}{7}\equiv \dfrac{4}{28}\equiv\dfrac{-27}{-3}\equiv 9\ $ by Gauss's algorithm.

$\!\!\bmod 31\!:\,\ \dfrac{1}{7}\equiv \dfrac{1}{-6}\,\dfrac{1}{4}\equiv \dfrac{-30}{-6}\,\dfrac{32}{4}\equiv 5\cdot 8\equiv 9$

As here: $ $ the freedom to choose $\rm\color{#c00}{even}$ residue reps $\!\bmod\!$ odds makes division by 2 easy:

$\!\!\bmod 31\!:\,\ \dfrac{1}{7}\equiv\dfrac{\color{#c00}{32}}{\color{#c00}{-24}}\equiv\dfrac{4}{-3}\equiv\dfrac{-27}{-3}\equiv 9$

By the fractional extended Euclidean algorithm, or associated equational form

$ \begin{align} \bmod 31\!:\ \ \dfrac{0}{31}\overset{\large\frown}\equiv\color{#c00}{\dfrac{1}7}\ \, &\!\!\!\overset{\large\frown}\equiv\color{#0a0}{\dfrac{-4}3}\overset{\large\frown}\equiv\color{#90f}{\dfrac{9}1}\\[.7em] \text{said equationally}\ \ \ \ [\![1]\!]\ \ \ \ 31\, x&\,\equiv \ 0\ \\ [\![2]\!] \ \ \ \ \ \ \color{#c00}{7\,x}&\ \color{#c00}{ \equiv\ 1}\!\!\!\\ [\![1]\!]-4\,[\![2]\!] \rightarrow [\![3]\!]\ \ \ \ \ \ \color{#0a0}{3\,x} &\ \color{#0a0}{\equiv\ {-}4}\ \\ [\![2]\!] - 2\,[\![3]\!] \rightarrow [\![4]\!]\, \ \ \ \ \ \ \ \ \color{#90f}{x}&\ \color{#90f}{ \equiv\ 9} \end{align}$

Below we explain the basic idea behind the method of Inverse Reciprocity.

$\!\!\bmod 31\!:\,\ n \equiv \dfrac{1}7\equiv \dfrac{1+31\color{#c00}k}7.\ $ For an exact quotient we seek $\,k\,$ with $\,7\mid 1\!+\!31k,\,$ i.e.

$\!\!\bmod 7\!:\,\ \begin{align}0&\equiv 1\!+\!31k\\ &\equiv 1 + 3k\end{align}\!$ $\iff\! \begin{align}3k&\equiv-1\\ &\equiv\,\ 6\end{align}\!$ $\iff \color{#c00}{k\equiv 2},\ $ so $\ n \equiv \dfrac{1\!+\!31(\color{#c00}2)}7\equiv 9\pmod{\!31}$

Or $ $ by Euler $\rm\ (a,m)=1 \Rightarrow\ a^{-1} \equiv a^{\phi(m)-1}\pmod{\! m},\,$ quickly computable by repeated squaring.

Remark $ $ The latter yields a simple closed form for CRT (Chinese Remainder Theorem)

$\quad$ if $\rm\,\ (m,n)=1\,\ $ then $\rm\quad \begin{eqnarray}\rm x\!&\equiv&\rm a\ \ (mod\ m)\\ \rm x\!&\equiv&\rm b\ \ (mod\ n)\end{eqnarray} \iff\ x\equiv a\,n^{\phi(m)}\!+b\,m^{\phi(n)}\ \ (mod\ mn)$

More generally see the Peirce decomposition.