An integer $a \pmod m$ has inverse if and only if $\gcd(a,m)=1$? An integer $a \pmod m$ has inverse if and only if $\gcd(a,m)=1$?
Why is this? I tried understanding it from my notes but I don't get it.
A thorough explanation would be greatly welcome.
Thanks for all the answers so far. I think my biggest problem is understanding why $\gcd(a,m)\neq1 \Longrightarrow \not\exists a^{-1}$.

If $\gcd(a,m)=1$, then we can find an $x$ and $y$ such that $ax+my=1$ through the Euclidean algorithm. Thus $ax =1-my \equiv 1 \pmod{m}$. Thus $a$ has an inverse.
Conversely, if $a \pmod{m}$ has an inverse then there exists an $x$ such that $ax \equiv 1 \mod{m}$, which is the same as saying that exists a $y$ such that $ax = 1+my$ or $ax-my=1$, which implies, by the Euclidean algorithm, that $\gcd(a,m)=1$
