This comes down to the following general result:
Theorem. Let $R$ be a ring. Then $ax = ay\text{ implies }x=y \Longleftrightarrow az=0\text{ implies }z=0.$
Proof. $\Rightarrow)$ Assume that whenever $ax=ay$, we can conclude $x=y$. Suppose $az=0$. Then $az=a0$, so this implies $z=0$.
$\Leftarrow)$ Suppose that whenever $az=0$, we have $z=0$. If $ax=ay$, then $a(x-y) = ax-ay = 0$, so $x-y = 0$; therefore, $x=y$. QED
That is, cancellation works whenever what you are cancelling is not a zero divisor (and more specifically, cancellation on the left/right works when what you are cancelling is not a left/right zero divisor).
In particular, when you are working in modular arithmetic $ab\equiv ac\pmod{m}\text{ implies }b\equiv c\pmod{m}\Longleftrightarrow az\equiv0\pmod{m}\text{ implies } z\equiv 0\pmod{m}.$
Proposition. Let $a$ and $m$ be positive integers. Then $\gcd(a,m)=1$ if and only if $az\equiv 0\pmod{m}$ implies $z\equiv 0\pmod{m}$.
Proof. If $\gcd(a,m)=1$ and $az\equiv 0\pmod{m}$, then $m|az$ and $\gcd(m,a)=1$, which implies $m|z$. Therefore $z\equiv 0\pmod{m}$.
Conversely, suppose $az\equiv 0\pmod{m}$ implies $z\equiv 0\pmod{m}$. Let $d=\gcd(a,m)$, and write $a=dk$, $m=d\ell$. Then $a\ell = dk\ell = mk\equiv 0\pmod{m}$, so $\ell\equiv0\pmod{m}$. Therefore, $m|\ell$, Since $m=k\ell$, $k=1$. QED.
Corollary. Let $a$, $b$, $c$, and $m$ be positive integers. Then $ab\equiv ac\pmod{m}$ implies $b\equiv c\pmod{m}$ if and only if $\gcd(a,m) = 1$.
So, first, you should not think of this as "division", but as "cancellation" (for example, one can cancel in the integers, even though there is no "division"). And you should think of "division" in general not as an entirely separate operation, but really as "multiplying by the multiplicative inverse". For example, in the rationals, you don't "really" divide by $3$, you multiply by $\frac{1}{3}$, which is the (unique) rational which, when multiplied by $3$, gives $1$; that is, the multiplicative inverse of $3$.