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

I'm having trouble understanding why for finding the inverse for $x\bmod n$, $\gcd(x, n)=1$ is a precondition. Obviously I've tried examples where the gcd is greater than one and I can't find $a$ for $ax \equiv _n 1$. I'm trying to prove to myself why this is the case.

I can mechanically say the following:

Find the modular inverse $a$ of $x\pmod n$

$$ax \equiv _n 1 \Leftrightarrow n \mid (ax-1)$$

And $n \mid (ax-1)$ implies that $(ax-1)=nk$ for some $k \in \mathbb Z $

After that I am stuck and I'm not sure if I'm going in the right direction.

Solution 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$

Solution 2:

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.