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.