6
$\begingroup$

Prove that the multiplicative inverse of $a$ modulo $m$ exists if and only if $a$ and $m$ are coprime.

Can someone help me with this?

$\endgroup$
  • 1
    $\begingroup$ $I'd like you to show some effort. What have you tried so far? Where are you stuck? $\endgroup$ – Stefan Mesken Aug 14 '14 at 14:10
6
$\begingroup$

Hint: $a,m$ coprime implies the existence of integers $r,s$ s.t. $ra+sm=1$ (lemma of Bezout).

Hint2:

If $ra=1$ mod $m$ then $m|ra-1$ so that $ra-1=sm$ for some integer $m$

$\endgroup$
  • $\begingroup$ i can prove this one. My problem is the other way round, which is if multiplicative inverse exists, then a,m are cop rime $\endgroup$ – user10024395 Aug 14 '14 at 14:33
  • $\begingroup$ The existence of multiplicative inverse implies the existence of integer $r,s$ with $ra+sm=1$. If $d=gcd(a,m)$ then $d$ divides $ra+sm=1$ so $d$ must be $1$. $\endgroup$ – Vera Aug 14 '14 at 14:38
5
$\begingroup$

Suppose there exists a multiplicative inverse q such that

$aq \equiv 1\ (mod\ m) \implies aq - 1 = mk \implies aq + mk_1 = 1 \implies gcd(a,m) = 1$ can be easily proven I will leave it as excerise to you how I reached that last step.

Now going the other side

Suppose that $gcd(a,m) = 1 \implies ay_1 + mq_1 = 1 \implies ay_1 \equiv 1 \ (mod\ m)$, so multiplicative inverse exists.

I have taken few short-cuts since some steps are trivial to complete but if you don't see it right away I can modify my answer.

$\endgroup$
  • 2
    $\begingroup$ would you mind explicitly stating how you got to the gcd(a, m)=1 step in your first proof? $\endgroup$ – Michelle Aug 5 '17 at 19:42
  • 1
    $\begingroup$ You can do it directly. Constructing gcd is as follows you can easily prove that $gcd(a,b) = min\{ au + mv : au + mv > 0\}$ Here we are considering the integers by well ordering principle such number exist. As integers begin with 1, so that is minimum such possible. $\endgroup$ – user111750 Aug 7 '17 at 19:22
  • $\begingroup$ You can do a more elementary argument, but this is as deep as you can get. $\endgroup$ – user111750 Aug 7 '17 at 19:22

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.