0
$\begingroup$

Find a multiplicative inverse of $a=11$ modulo $m=13$.

What is this saying?

This seems like such a simple question, I just don't understand what it is asking for.

An additional question related to this I have is:

If $a$ has a multiplicative inverse modulo $m$, explain why $\gcd(a,m)=1$.

Is this also saying $ab \equiv 1 (mod \space m)$? Do $a$ and $m$ have to be prime since the $\gcd(a,m)=1$?

Thanks again.

2 Answers 2

2

It's asking to find $b$ such that

$$ab \equiv 1 \pmod m$$

Hint: Euclidean algorithm


Edit:

Suppose that $a$ has a multiplicative inverse mod $m$. That is, there is a number $b$ such that $ab = 1 + km$ (for some $k \in \mathbb{Z}$). Hence, $ab - km = 1$.

If $a$ and $m$ have a common divisor $d$, then $d$ is a divisor of $ba − km$ and hence of 1.

Therefore $d=1$, which means that $\gcd(a,m)=1$.

And, no $a$ and $m$ don't have to be prime! Just co-prime.

  • 0
    So, for $11b \equiv 1 (mod 13)$ we get $b=6$ This doesn't seem like the multiplicative inverse. Where do I go from here? Thanks.2012-10-16
  • 0
    @student.llama No, that's it! The modular multiplicative inverse of 11 modulo 13 is 6.2012-10-16
  • 0
    **That** is the multiplicative inverse since $$11\cdot 6=66=1+5\cdot 13=1\pmod {13}$$2012-10-16
  • 0
    Oh, ok, thanks! Could you take a look at what I added to the OP, if you haven't already?2012-10-16
  • 0
    @student.llama See my edit :)2012-10-16
0

$11^2=121\equiv 4\pmod{13}$

$11^3\equiv4\cdot 11\equiv 5$

$11^4=(11^2)^2\equiv 4^2=16\equiv 3$

$11^5\equiv3\cdot11=33\equiv 7$

$11^6\equiv7\cdot 11= 77=-1$

$\implies 11\cdot 11^5\equiv-1\implies (11)^{-1}\equiv -11^5\equiv -7\equiv 6\pmod{13}$


Alternatively, using convergent property of continued fraction,

$\frac{13}{11}=1+\frac 2{11}=1+\frac1{\frac{11}2}=1+\frac1{5+\frac12}$

So, the last but one convergent is $1+\frac15=\frac 6 5$

So, $11\cdot 6-13\cdot 5=66-65=1\implies 11\cdot 6\equiv 1\pmod{13}$ $\implies (11)^{-1}\equiv 6\pmod{13}$