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