Cancellation law and the existence of modular inverses

Since $\gcd(c,m)=1$, Bézout's identity (a consequence of the Euclidean algorithm) guarantees $\exists\, u,v \in \mathbb{Z}:\ cu+mv=1$: there exist integers $u,v$ with $cu+mv=1$.

Multiply both sides of $ac\equiv bc\pmod m$ by $u$: $acu\equiv bcu\pmod m$. Now substitute $cu=1-mv$: the left side becomes $a(1-mv)=a-amv$, and since $amv$ is a multiple of $m$, $a(1-mv)\equiv a\pmod m$; likewise the right side $b(1-mv)\equiv b\pmod m$. Hence $a\equiv b\pmod m$, proving cancellation.

Moreover, taking $a=1,b=0,c=c$ is not needed — directly, $cu = 1-mv \equiv 1 \pmod m$ by the same substitution, so $u$ itself is the multiplicative inverse of $c$ modulo $m$: this is exactly the object whose existence Theorem statement claims.

The hypothesis $\gcd(c,m)=1$ is essential: take $c=4,\ m=6$ (so $\gcd(4,6)=2\neq1$). Then $4\times 2=8\equiv 2\pmod 6$ and $4\times 5=20\equiv 2\pmod 6$, so $4\times2\equiv 4\times5\pmod 6$, yet $2\not\equiv 5\pmod 6$ — cancellation genuinely fails once the coprimality hypothesis is dropped.