Why only numbers coprime with n in A mod n have modular inverse?

Question

Why do only the numbers coprime to n (numbers that share no prime factors with n) have a modular inverse (mod n)? Can anyone intuitively explain it?

Answer 1

Say $x$ is not coprime to $n$. Let $p$ be a common factor of $x,n$. Then we can write $x=py,n=pm$. This shows that $x$ is a "zero divisor", i.e., $$xm\equiv 0\mod n.$$ It is a general fact that zero-divisors cannot have inverses.

In particular, here is a simple proof by contradiction of this fact: Assume that for some $z$, we have $zx\equiv 1\mod p$. This gives the following two equations: $$zxm \equiv 1m\not\equiv 0\mod n$$ $$zxm \equiv z0\equiv 0 \mod n$$ which is clearly impossible.

For intuition, I think it is helpful to note that if $x,p$ are coprime then $x,2x,3x,\ldots$ is a permutation of $0,1,2,\ldots, p-1$ (which in particular shows that $x$ has a multiplicative inverse), whereas this cannot work for zero-divisors.