In $\Bbb Z/m\Bbb Z,$ if $a$ is not invertible then it is a zero divisor

Solution 1:

Hint $ $ unit $a\!\iff\! x\mapsto ax$ onto $\!\iff\! x\mapsto ax\,\ 1\!-\!1\!\iff\! a$ cancellable $\!\iff\! a$ not zero-divisor

See also the following.

Theorem $\ $ The following are equivalent for integers $\rm\:c,\, m.$

$(1)\rm\ \ \ gcd(c,m) = 1$
$(2)\rm\ \ \ c\:$ is invertible $\rm\,(mod\ m)$
$(3)\rm\ \ \ x\to cx+d\:$ is $\:1$-$1\:$ $\rm\,(mod\ m)$
$(4)\rm\ \ \ x\to cx+d\:$ is onto $\rm\,(mod\ m)$

Proof $\ (1\Rightarrow 2)\ $ By Bezout $\rm\, gcd(c,m)\! =\! 1\Rightarrow cd\!+\!km =\! 1\,$ for $\rm\,d,k\in\Bbb Z\,$ $\rm\Rightarrow cd\equiv 1\!\pmod{\! m}$
$(2\Rightarrow 3)\ \ \ \rm cx\!+\!d \equiv cy\!+\!d\,\Rightarrow\,c(x\!-\!y)\equiv 0\,\Rightarrow\,x\!-\!y\equiv 0\,$ by multiplying by $\rm\,c^{-1}$
$(3\Rightarrow 4)\ \ $ Every $1$-$1$ function on a finite set is onto (pigeonhole).
$(4\Rightarrow 1)\ \ \ \rm x\to cx\,$ is onto, so $\rm\,cd\equiv 1,\,$ some $\rm\,d,\,$ i.e. $\rm\, cd+km = 1,\,$ some $\rm\,k,\,$ so $\rm\gcd(c,m)=1$

See here for a conceptual proof of said Bezout identity for the gcd.

Solution 2:

Suppose $a$ is not a unit.

Then $\gcd(a,m)=d\ (>1)$.

Then, $\left(\frac{m}{d}\right)\cdot a=0\ (\mod m)$.

Thus, $a$ is a zero divisor.

Solution 3:

Let's write $R=\Bbb Z/m\Bbb Z$, and consider $a\in R$.

If $ar\neq as$ for all $r,s\in R$ $r\neq s$, then $\{ar\mid r\in R\}=R$, so there's an element $r$ such that $ar=1$, and $a$ is a unit.

If we require $a$ to be a nonunit, then the above case cannot happen and so there exists $r,s\in R$ such that $ar=as$ but $r\neq s$.

Can you see how to extract $t\neq 0$ such that $at=0$ from this?