An integer $a \pmod m$ has inverse if and only if $\gcd(a,m)=1$? [duplicate]

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$


Everything is based on Bézout's theorem: $$\gcd(a,m)=1\iff \exists\, u,v\in\mathbf Z\enspace \text{such that}\enspace ua+vm=1$$ This theorem shows that, if $\gcd(a,m)=1$, then $vm\equiv 1\mod a$.

Conversely, if $\,vm\equiv 1\mod a$, it means there exists $u\in\mathbf Z$ such that $vm=1+ua$, whence $-ua+vm=1$, so that $\gcd(a,m)=1$.


$\exists x \in \mathbb{Z}$ s.t. $ ax \equiv 1$ mod $m \iff \exists n \in \mathbb{Z}$ s.t. $ax - nm = 1$.

Then if we let $d = gcd(a,m)$:

$d$ $| a$ and $d$ $| m$ so $d$ $|(ax-nm)$ and thus $d$ $|1$ and so $d = 1$

Conversely if $ d = 1$, be Bézout's Lemma, we can find $n,x \in \mathbb{Z}$ s.t. $ax - mn = 1$ as required.