2
$\begingroup$

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

Edit:
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"?

Questions:

  • How to prove the proposition above?
  • How many different proofs can one have?

4 Answers 4

3

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.

  • 0
    Ah, I made a mistake for i$n$terpreting the "if" part. Now I think it corrected.2011-07-03
1

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

1

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.

0

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\:.$