Proving that modular inverse only exists when $\gcd(n,x)=1$

If there is an inverse of $x \bmod n$, that gives us a number $y$ so that $xy \equiv 1 \bmod n$. That means that $xy=kn+1$, or (rearranging) that $xy-kn=1$.

Now for any common divisor, $c$, of $x$ and $n$ we will have that $c \mid (xy-kn)$ which gives $c\mid 1$, that is, $c=1$. So that is an outcome - and therefore a requirement - of finding the inverse of $x \bmod n$

Another way to see that this reveals something interesting about the structure of fields.

If $\gcd(n,x)=c$ then we can look at $y=\frac{x}{c}$. Clearly $xy=n$, but then $xy=0\pmod{n}$. For $c\neq 1$, this makes $x$ a zero-divisor - a number that isn't zero that when multiplied by another non-zero number gives zero. We can see that zero divisors aren't invertable (in general, not just in modular arithmetic) as follows:

Take $ab=0$ for $a,b\neq 0$. Assume $\exists a^{-1}$ such that $a^{-1}a=1$. Then $b=a^{-1}ab=a^{-1}0=0$ which is a contradiction since we assumed that $a,b\neq 0$.

It turns out that being a zero divisor exactly encapsulates what it means to be non-invertable, as show by the following theorem:

Theorem: Let $(R, +,\cdot)$ be a ring with identity. Then $(R,+\cdot)$ is a field if and only if $R$ contains no zero divisors.