How to show that "If cancellation laws hold in $\mathbb{Z}_n$, then $n$ must be prime" I was  assigned to prove that the following statements are equivalent:


*

*$\mathbb{Z}_n$ has no zero divisors.

*$\mathbb{Z}_n$ is an integral domain.

*The cancellation laws hold in $\mathbb{Z}_n$

*$n$ is prime.


For the proof of $(1)\implies (2)$, $(2)\implies (3)$ and $(4)\implies (1)$ I encountered no problem.
I am having a difficulty in proving the implication $3\implies 4$. But I found a counterexample. For instance since $n=4$ is not prime, then we have in $\mathbb{Z}_4$:
$2(3)=2(1)=2$ but $3\neq 1$. 
So I assume that the proof is via contradiction. 
Here is my attempt:
Let $a\neq 0$ be an element of $\mathbb{Z}_n$. Since cancellation laws hold then
$ab=ac\implies b=c$.
This means that $b\equiv c(mod\ n)$ or $n\mid(b-c)$.
Now suppose $n$ is composite. Then $b-c=kn$ for $k<b-c<n$.
From here, I do not know how to proceed. Is my proof flow correct? If not how can we prove the implication $(3)\implies (4)$.
Thanks in advance for all your help.       

You are almost there, here's a hint: suppose that $n$ is not prime, so that $n = st$ with $s,t \geq 1$. Look at this equation modulo $n$.

 Derive a contradiction from the fact that $st \equiv 0 = s \cdot 0\pmod{n}$ but $0 < s \neq n$ and in particular, $n | s$.

