What is $5^{-1}$ in $\mathbb Z_{11}$?

I am trying to understand what this question is asking and how to solve it. I spent some time looking around the net and it seems like there are many different ways to solve this, but I'm still left confused.

What is the multiplicative inverse of $5$ in $\mathbb Z_{11}$. Perform a trial and error search using a calculator to obtain your answer.

I found an example here:

In $\mathbb Z_{11}$, the multiplicative inverse of $7$ is $8$ since $7 * 8 \equiv 56 \pmod {11}$.

This example is confusing to me because $1 \pmod {11} \equiv 1$. I don't see how $56$ is congruent to $1 \pmod {11}$.

• $56=5\cdot11+1$ Sep 9 '15 at 19:30
• 9 is inverse of 5 in $Z_{11}$
– R.N
Sep 9 '15 at 19:31
• Note that $5\cdot 2=10\equiv -1\pmod{11}$. So $-2$, aka $9$, will do the job. Sep 9 '15 at 19:41

The modular inverse of $5$ modulo $11$ is the number $x$ that satisfies $5x \equiv 1 \pmod{11}$. You are supposed to find this number by trial-and-error, i.e. try out all the numbers from $1$ to $10$ an check which number satisfies the condition.

56 mod 11=1, because 56=55 (multiple of 11)+1

So the answer is 9, since $$9*5= 44+1$$

You may want to read up on modular arithmetic in order to approach this problem. For every numbers $k$ and $n$, there are infinitely many numbers $m$ such that $m\equiv k (\mod n)$, because $m=k+nt$ works for every $t$!

In $\mathbb{Z}_{11}$ (note: the notation $\mathbb{Z}/11\mathbb{Z}$ is generally considered slightly better), our elements are actually equivalence classes: $[0]\in\mathbb{Z}_{11}$ is the set of all numbers $m$ such that $m=11t$ for some $t\in\mathbb{Z}$, $[1]\in\mathbb{Z}_{11}$ is the set of all numbers $m$ such that $m=11t+1$ for some $t\in\mathbb{Z}$, and so on.

Your question is asking you to look at the representatives $x\in\{0,1,2,3,4,5,6,7,8,9,10\}$ and try to choose $x$ so that $5x=11t+1$ for some $t\in\mathbb{Z}$; i.e. find $x$ so that $5x\equiv 1(\mod 11)$. In particular, it wants you to just multiply each $5$ by each number in the above set, and then figure out which of these results can be written in the form $11t+1$ for some $t\in\mathbb{Z}$.

Here is a general method for finding the inverse of $a$ in $Z_n$:

• Set $x_1=1$
• Set $x_2=0$
• Set $y_1=0$
• Set $y_2=1$
• Set $r_1=n$
• Set $r_2=a$
• Repeat until $r_2=0$:
• Set $r_3=r_1\bmod{r_2}$
• Set $q_3=r_1/r_2$
• Set $x_3=x_1-q_3\cdot{x_2}$
• Set $y_3=y_1-q_3\cdot{y_2}$
• Set $x_1=x_2$
• Set $x_2=x_3$
• Set $y_1=y_2$
• Set $y_2=y_3$
• Set $r_1=r_2$
• Set $r_2=r_3$
• If $y_1>0$ then output $y_1$, otherwise output $y_1+n$

And here is an equivalent code in C:

int Inverse(int n,int a)
{
int x1 = 1;
int x2 = 0;
int y1 = 0;
int y2 = 1;
int r1 = n;
int r2 = a;

while (r2 != 0)
{
int r3 = r1%r2;
int q3 = r1/r2;
int x3 = x1-q3*x2;
int y3 = y1-q3*y2;

x1 = x2;
x2 = x3;
y1 = y2;
y2 = y3;
r1 = r2;
r2 = r3;
}

return y1>0? y1:y1+n;
}


$5\cdot 2=10=-1$ modulo $11$. It follows that $5\cdot(-2)=1$ modulo $11$. This means that $-2$ is the inverse of $5$ in ${\mathbb Z}_{11}$. Depending on the notation you use for the individual elements of ${\mathbb Z}_{11}$ the answer to your question could as well be $9$.

For an alternative method, use Fermat's Little Theorem, since $5$ and $11$ are distinct primes. Then there is no trial and error required.

Then $5^{10}\equiv 1\pmod{11}$ i.e. $5\cdot5^9\equiv 1\pmod{11}$, so $5^{-1}\equiv 5^9\pmod{11}$ and

$$5^9\equiv 25\times5^7\equiv3\times5^7\equiv9\times5^5\equiv27\times5^3\equiv5\times5^3\equiv3\times5^2\equiv9\pmod{11}$$

Hence $\boxed{5^{-1}=9}$ in $\mathbb{Z}_{11}$.