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