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?

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$

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.