1
$\begingroup$

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

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

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.

$\endgroup$
0
0
$\begingroup$

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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;
}
$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.