Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following proposition:

A nonzero element $m\in{\bf Z}_n$ is a zero divisor if and only if $m$ and $n$ are not relatively prime.

I don't know if this is a classical textbook result. (I didn't find it in Gallian's book).

For the "only if" part, one may like to use the Euclid's lemma. But I cannot see how can one prove the "if" part:

If $m_1>0$, $(m_1,n)=d>1$, and $n|m_1m_2$, then $n\nmid m_2$.

The "if" part, should be: If $m_1>0$ and $(m_1,n)=d>1$, then there exists $m_2$ such that $n|m_1m_2$, and $n\nmid m_2$.

Does one need any other techniques other than "divisibility"?


  • How to prove the proposition above?
  • How many different proofs can one have?
share|cite|improve this question
up vote 3 down vote accepted

You have been trying to prove that

"If $m_1>0$, $(m_1,n)=d>1$, and $n|m_1m_2$, then $n\nmid m_2$."

But this is general false. Counterexamples are easy to find. Take for example $m_1=2$, $n=2$, $m_2=2$.

A good approach to solving the original problem is to look at what happens in few concrete cases. Take for example $m=2$, $n=6$. You want to show $m$ is a zero divisor in $\mathbb{Z}_n$. Can you come up with a number $x$ not congruent to $0$ modulo $6$ such that $2x \equiv 0$? Sure, easy, $x=3$ will do.

What about $m=12$, $n=14$? Sure, we want multiply $12$ by some $x$ not divisible by $14$ but such that the result is divisible by $14$. Well, the $2$ in $12$ helps, we only need to multiply $12$ by $7$.

Look at a few more examples. We can after a while see that the "$d$" that is common to $m$ and $n$ can be used to come up with an $x$ not divisible by $n$ such that $mx$ is divisible by $n$. Then the formal proof writes itself.

share|cite|improve this answer
Ah, I made a mistake for interpreting the "if" part. Now I think it corrected. – Jack Jul 3 '11 at 18:02

Let $d=GCD(m,n)>1$ and write $n=dk$. Thus $1<k<n$ so that $k\not\equiv0\bmod n$. Yet $km\equiv0\bmod n$ since $d\mid m$.

share|cite|improve this answer

Okay so it is given that $(m,n) = d > 1$ and we wish to prove that $m$ is a zero divisor. Note that both $\frac{m}{d}>1$ and $\frac{n}{d}>1$ are in $Z_n$ and as $(\frac{m}{d})n=0$ in $Z_n$(being a multiple of n) so we have $0=(\frac{m}{d})n=m(\frac{n}{d})$, i.e. m is indeed a zero divisor.

share|cite|improve this answer

HINT $\rm\displaystyle\quad 1 < d\ |\ m, n\ \ \Rightarrow\ \ n\ |\ m\:\frac{n}d\:,\ $ but $\rm\displaystyle\ \ n\nmid m\:,\ \ n\nmid\frac{n}d\ $

i.e. $\rm\ \ mod\ n\:,$ $\rm\displaystyle\:\ \ m\:\frac{n}d\ =\ \frac{m}d\: n\ =\ 0\:,\ $ but $\rm\displaystyle\ m\ne 0\:,\ \frac{n}d\:\ne 0\:,\ $ so $\rm\:m\:$ is a zero-divisor in $\rm\:\mathbb Z/n\:.$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.