I know that in order to have an inverse of $x \pmod{m}$ we need $\gcd(x,m)=1$ and $x^{-1}$ can be found directly from extended euclidian algorithm by considering $ax+bm=1$ Modulo $m$.
But assuming $\gcd(x,m) = z \neq 1$, then isn't there a possibility that $z\mid a$ and $z\mid b$ thus we can divide both sides by $z$ and obtain $x^{-1}$. If not then can we generally assume that $z\nmid a$ or $z \nmid b$?
If $\gcd(x,m)=z$ and $ax+bm=z$, then $z$ already divides both $x$ and $m$. If $z$ additionally divided $a$ and $b$, then both terms of $ax+bm$ would be divisible by $z^2$, so $z$ would be divisible by $z^2$. This is impossible for $z>1$.