# Finding the inverse of a number under a certain modulus

How does one get the inverse of 7 modulo 11?

I know the answer is supposed to be 8, but have no idea how to reach or calculate that figure.

Likewise, I have the same problem finding the inverse of 3 modulo 13, which is 9.

The inverses can be computed using the extended euclidean algorithm. As long as $\gcd(x,n) = 1$ the inverse $x^{-1} \bmod n$ exists and is $y$ from the extended euclidean algorithm where $$xy + kn = 1 = \gcd(x,n)$$ For example we get $$7\cdot 8 - 5\cdot 11 = 1\\ 9 \cdot 3 - 2\cdot 13 = 1$$

Note that you can also obtain negative numbers, for example $$7\cdot (-3) + 2\cdot 11 = 1$$ In this case you can use congruences $\bmod n$ to obtain the canonical inverse: $-3 \equiv 8 \pmod{11}$

• Thanks but I'm really struggling with this, could you provide me with a sample, i be stuck for two days trying to figure it out – Dan W May 4 '15 at 12:07
• @DanW What part of this do you struggle with? – AlexR May 4 '15 at 12:09
• Basically, i want to know the inverse of 7 within mod 11, i need a figure!!, i understand the gcd and what it is doing/proving. – Dan W May 4 '15 at 12:20
• @DanW Can you show me what the extended euclidean algorithm gives you wen used for $\gcd(7,11)$? – AlexR May 4 '15 at 12:23
• A B Q R 11 7 1 4 7 4 1 3 4 3 1 1 – Dan W May 4 '15 at 12:28

To find the inverse of $7$, $\pmod{11}$, you must find a solution to $7x\equiv 1 \pmod{11}$. (Then $x$ satisfies the definition of inverse.)

As suggested in other answers, one way to do this is with the extended Euclidean algorithm, and in fact this is the best general purpose algorithm for this type of problem.

But for small values, you can also try 'adding the modulus':

$7x\equiv 1\equiv 12\equiv 23\equiv 34\equiv 45\equiv 56 \pmod{11}$.

Then from $7x\equiv 56\pmod{11}$, we can cancel $7$, obtaining $x\equiv 8 \pmod{11}$.

Here's an illustration of finding the multiplicative inverse of $37 \bmod 100$ using the extended Euclidean algorithm. (I used bigger numbers for this example so that the relationships are a little clearer).

On each line, $n=100s+37t$. We start the table with two lines giving $n=100$ and $n=37$ in the obvious way. Then $q$ gives the rounded-down ratio of the current and previous value of $n$. Using this, the next line is calculated by subtracting $q$ copies of the current line entries from the previous line entries.

$$\begin{array}{c|c|c|c} n & s & t & q \\ \hline 100 & 1 & 0 & \\ 37 & 0 & 1 & 2 \\ 26 & 1 & -2 & 1 \\ 11 & -1 & 3 & 2 \\ 4 & 3 & -8 & 2 \\ 3 & -7 & 19 & 1 \\ 1 & 10 & \color{red}{-27} & 3 \\ \end{array}$$

On the last line, $1 = 10\times 100 + (-27)\times 37$, so $\color{red}{-27}\times 37 \equiv 1 \bmod 100$

Bringing the result positive, $-27 \equiv \color{red}{73} \bmod 100$. And $37 \times 73 = 2701 \equiv 1 \bmod 100 \quad \checkmark$.

As you can perhaps see, you don't actually need to calculate the $s$ values at all to get the modular inverse. I left them in to help understand the table.

The corresponding tables for your particular questions: $$\begin{array}{c|c|c|c} n & s & t & q \\ \hline 11 & 1 & 0 & \\ 7 & 0 & 1 & 1 \\ 4 & 1 & -1 & 1 \\ 3 & -1 & 2 & 1 \\ 1 & 2 & \color{red}{-3} & 3 \\ \end{array}$$ and $7^{-1} \equiv -3 \equiv \color{red}8 \bmod 11$. $\quad 7\times 8 = 56 = 55+1\quad \checkmark$

$$\begin{array}{c|c|c|c} n & s & t & q \\ \hline 13 & 1 & 0 & \\ 3 & 0 & 1 & 4 \\ 1 & 1 & \color{red}{-4} & 3 \\ \end{array}$$ and $3^{-1} \equiv -4 \equiv \color{red}9 \bmod 13$. $\quad 3\times 9 = 27 = 26+1\quad \checkmark$

${\rm mod}\ 11\!:\,\ \dfrac{1}7\equiv \dfrac{12}{-4}\equiv -3\$ (see Gauss's algorithm. for an algorithmic version of this).

Or, compute the Bezout identity $\,\gcd(11,7) = 2(11)-3(7) = 1\,$ by the Extended Euclidean Algorithm  (see here for a convenient version).  Thus $\ {-}3(7)\equiv 1\pmod{11}$

${\rm mod}\ 13\!:\,\ \dfrac{1}3\equiv \dfrac{-12}{3}\equiv -4\$

Generally inverting $\,a\,$ mod $\,m\,$ is easy if $\,a\mid m\pm1,\$ i.e. $\ m = ab\pm 1$

${\rm mod}\ ab-1 \!:\qquad ab\equiv 1\,\Rightarrow\, a^{-1}\equiv b$

${\rm mod}\ ab+1 \!:\,\ a(-b)\equiv 1\,\Rightarrow\, a^{-1}\equiv -b$

Above are special cases: $\,3\mid 13\!-\!1\$ and $\ 7\equiv -4\mid 11\!+\!1$

To find the inverse of $7$ modulo $11$, we must solve the equivalence $7x \equiv 1 \pmod{11}$. To do this, we use the Extended Euclidean Algorithm to express $1$ as a linear combination of $7$ and $11$. The coefficient of $7$ will be the inverse modulo $11$. By the Euclidean Algorithm, \begin{align*} 11 & = 1 \cdot 7 + 4\\ 7 & = 1 \cdot 4 + 3\\ 4 & = 1 \cdot 3 + 1\\ 3 & = 3 \cdot 1 \end{align*} We now take the equation $4 = 1 \cdot 3 + 1 = 3 + 1$, solve for $1$, then work backwards until we obtain $1$ as a linear combination of $7$ and $11$. \begin{align*} 1 & = 4 - 3\\ & = 4 - (7 - 4)\\ & = 2 \cdot 4 - 7\\ & = 2(11 - 7) - 7\\ & = 2 \cdot 11 - 3 \cdot 7 \end{align*} Since $2 \cdot 11 - 3 \cdot 7 = 1$, $$-3 \cdot 7 = 1 - 2 \cdot 11 \Longrightarrow -3 \cdot 7 \equiv 1 \pmod{11}$$ Hence, $-3$ is the inverse of $7 \pmod{11}$. To express the inverse as one of the residues $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, we add $11$ to $-3$ to obtain $-3 + 11 \equiv 8 \pmod{11}$. Hence, $7^{-1} \equiv 8 \pmod{11}$.

Check: $7 \cdot 8 \equiv 56 \equiv 1 + 5 \cdot 11 \equiv 1 \pmod{11}$.

To verify you understand the algorithm, try to find the inverse of $3$ modulo $13$.

As said by AlexR, you can find $x,y\in\mathbb Z$ with $7x+11y=1$ using Extended Euclidean algorithm (see this answer for how to best use it).

You can also use elementary modular arithmetic 'tricks':

$\bmod{11}\!:\ 7x\equiv 1\equiv -21\stackrel{:7}\iff x\equiv -3\equiv 8$.

$\bmod{11}\!:\ 7x\equiv -4x\equiv 1\equiv 12\stackrel{:(-4)}\iff x\equiv -3\equiv 8$.

We could divide by $7$ and $-4$ because $(7,11)=(-4,11)=1$.