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

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?

• $I'd like you to show some effort. What have you tried so far? Where are you stuck? – Stefan Mesken Aug 14 '14 at 14:10 ## 2 Answers 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$• i can prove this one. My problem is the other way round, which is if multiplicative inverse exists, then a,m are cop rime – user10024395 Aug 14 '14 at 14:33 • 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$. – Vera Aug 14 '14 at 14:38 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. • would you mind explicitly stating how you got to the gcd(a, m)=1 step in your first proof? – Michelle Aug 5 '17 at 19:42 • 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. – user111750 Aug 7 '17 at 19:22
• You can do a more elementary argument, but this is as deep as you can get. – user111750 Aug 7 '17 at 19:22