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

Question

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

Note that $5\cdot 2=10\equiv -1\pmod{11}$. So $-2$, aka $9$, will do the job. — André Nicolas, Sep 09 '15 at 19:41

score 1 · Answer 1 · answered Sep 09 '15 at 19:36

1

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.

answered Sep 09 '15 at 19:36

Dominik

19,963

score 0 · Answer 2 · answered Sep 09 '15 at 19:39

0

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

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

answered Sep 09 '15 at 19:39

limepickle

101

score 0 · Answer 3 · answered Sep 09 '15 at 19:41

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

score 0 · Answer 4 · answered Sep 09 '15 at 19:41

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;
}

score 0 · Answer 5 · answered Sep 09 '15 at 19:44

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

score 0 · Answer 6 · answered Sep 09 '15 at 19:47

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

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

6 Answers6