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

Let us consider the ring $\mathbb{Z}_n$ where $\bar{m}\in\mathbb{Z}_n$

Could anyone help me prove that $\bar{m}$ is a zero divisor in $\mathbb{Z}_n$ if and only if $m,n$ are not coprime

So far I have:

Assume $\exists \bar{a}: \bar{m} \bar{n}=n \mathbb{Z} \Rightarrow$ for some $b\in\mathbb{Z}:am=bn$

I then assumed $n,m$ were coprime and attempted to use $\exists a',b'\in \mathbb{Z}:a'm+b'n=1$ to come to a contradiction, however haven't found one, the most promising thing I have found so far is that

$a=n(a'b+ab')$ and $b=m(a'b+ab')$ $\Rightarrow n|a$ and $m|b$

-

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.

-
Ah god, that's obvious isn't it. So $m,n$ being coprime forces $\bar{a}$ to be zero, thanks for making that connection for me, bugging the hell out of me. –  Freeman Sep 27 '11 at 15:04

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)$$

-
As always Bill very enlightening :) Thanks for your help! –  Freeman Sep 27 '11 at 22:04

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.

-
Do you think you could elaborate as why we can take $b,k$ to be strictly less than $n$? And why the LCM of $m,n$ being less than $mn$ implies there are not coprime? –  Freeman Sep 27 '11 at 14:21
We can take k to be less than $n$ because it is only defined as a residue class mod $n$. Any such residue class contains at least one element less than $n$. The same holds for $m$. Since $k$ and $m$ are less than $n$, $b$ must be less than n also for otherwise $nb > mk$. In regards to the LCM, if $n$ and $m$ ar enot equal and share a factor $p$, then we can write $m = ap$, $n = bp$ for integers $a$ and $b$, at least one of which is greater than 1. Therefore $\frac{nm}{ab}$ is a multiple of $n$ and of $m$ which less than $nm$. –  user15464 Sep 27 '11 at 20:46
Thanks! that is of great help! –  Freeman Sep 27 '11 at 22:00

Maybe you can divide this out into two cases, when $n$ is prime and when it is not.

Case 1:

If $n$ is a prime number then $\mathbb{Z}_n$ will be a commutative division ring with a unit, so if $ab \equiv 0$ mod $p$ for $a,b \in \mathbb{Z}_n$, then this means that by euclid's lemma that $p$ divides $a$ or $p$ divides $b$ so that $a$ or $b$ are equivalent to zero mod $p$.

In particular since any element in $\mathbb{Z}_n$ will be coprime to $n$, no element in $\mathbb{Z}_n$ will be a zero divisor by the result above (Recall that an element $a \neq 0$ in a ring is a zero-divisor if $ab = 0$ for some $b \neq 0$ in the ring).

I think it makes no sense to talk of the other direction for the only time when a number $m$ is not coprime to a prime $n$ is when $m$ is a multiple of $n$, but this is ridiculous for such an $m$ is not in $\mathbb{Z}_n$.

Case 2:

Suppose $n$ is not a prime number. Can you try to work this out for yourself?

-
Thanks for this! Only problem is euclids lemma is not part of our course so far, so I should really find a more elementary way –  Freeman Sep 27 '11 at 14:51
@LHS That is not part of the course is trivial: Euclid's Lemma can be derived from Bezout's Identity which you used above. Why should you not be allowed to use it then? –  fpqc Sep 27 '11 at 16:06
Oh no reason really, it's just our tutors like us to stick to using the theorems we already know to answer questions in specific ways. For instance for several months we had to pretend to know nothing about determinants. We will likely cover it soon. –  Freeman Sep 27 '11 at 22:02
I don't agree with not allowing you to use corollaries of theorems that you know.... With regards to determinants you can try to do without them. –  fpqc Sep 27 '11 at 22:10