Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  student.llama Oct 16 '12 at 16:40
    
@student.llama No, that's it! The modular multiplicative inverse of 11 modulo 13 is 6. –  Alex Oct 16 '12 at 16:42
    
That is the multiplicative inverse since $$11\cdot 6=66=1+5\cdot 13=1\pmod {13}$$ –  DonAntonio Oct 16 '12 at 16:43
    
Oh, ok, thanks! Could you take a look at what I added to the OP, if you haven't already? –  student.llama Oct 16 '12 at 16:47
    
@student.llama See my edit :) –  Alex Oct 16 '12 at 16:59

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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