why inverse of a number module n exists if gcd(number, module) = 1?

Question

I have difficulties thinking the relationship between inverse of a number and gcd.

If I want to know if a specific number module n has an inverse I check if gcd between the number and the module is 1, why?

a≡b(n) has inverse only if  gcd(a,n)=1

I know that the result of gcd(a,n) is the rest of Euclidean division, why does it prove that a has an inverse module n?

Answer 1

This is because of Bézout's Identity: for $n, m \in {\mathbb Z}$ there are $x, y \in {\mathbb Z}$ such that $x n + y m = \gcd(n,m)$.

Applying this to $n$ and $m$ that have greatest common divisor 1, you get that there are $x, y$ such that $x n + y m = 1$. So, in particular, $x n \equiv 1 \pmod m$, which means that $n$ is invertible modulo $m$.

To actually find the $x, y$ from Bézout's Identity, use the Extended Euclidean Algorithm.

Answer 2

That is because of Bézout's identity: $\gcd(a,n)=1$ if and only if there exist $u,v\in\mathbf Z$ such that $ua+vn=1$. Reducing this relation modulo $n$ yields $$u\bmod n\cdot a\bmod n\equiv 1\bmod n. $$ Conversely, if $a$ has an inverse $u$ mod $n$, it leans there exists $b\in \mathbf Z$ such that $$ua=1+bn,\enspace\text{whence}\quad ua-bn=1,$$ which proves $a$ and $n$ are coprime.