How to prove $\bar{m}$ is a zero divisor in $\mathbb{Z}_n$ if and only if $m,n$ are not coprime

Solution 1:

You're almost there. Suppose that $m$ and $n$ are coprime and that $ma$ is a multiple of $n$. From $a'm+b'n=1$ you get $a'ma+b'na=a$. Then, $a$ is a multiple of $n$, that is $\bar a=\bar 0$ and $m$ is not a zero divisor.

Solution 2:

Hint $\, $ Recall every element of a finite ring is either a unit or zero-divisor, e.g. see here or here. Thus the contrapositive equivalent of your statement is $\rm\,\gcd(m,n) = 1\,$ iff $\rm\:m\:$ is unit. By Bezout

$$\rm \gcd(m,n) = 1\iff\ \exists\ \: j,k\in\mathbb Z:\ j\ m + k\ n = 1\iff \ \exists\ \: j\in \mathbb Z:\ j\ m\equiv 1\ \ (mod\ n)$$

Solution 3:

If $m$ is not coprime with $n$, let $b$ be their greatest common divisor. Then $m \frac{n}{b}$ is an integer multiple of $n$, so equals $0 \mod n$. Therefore $\bar m$ is a zero divisor (since $\frac{n}{b}$ is not equal to $0 \mod n$.

Conversely, if $m$ is a zero divisor, we have $\bar m \bar k = 0 \mod n$ for some $k \not= 0 \mod n$, ie. $mk = nb$ for some integer $b$. We may take $b$ and $k$ to be less than or equal to $n$; since $k\not= 0 \mod n$, $k$ is striclty less than $n$. Therefore the least least common multiple of $n$ and $m$ is strictly less than $nm$. Hence $n$ and $m$ are not coprime.