# $n$ is prime $\Leftrightarrow [a][b]=0\Rightarrow [a]=[b]=0$ [duplicate]

I'm stuck on the following exercise from Herstein's "Topics in Algebra":

"show that ($n$ is prime) $\Leftrightarrow ([a][b]=\Rightarrow [a]=[b]=)$ in $J_n$".

for the rightward implication I have:

$[a][b]=[ab]=\Rightarrow n|ab\Rightarrow n|a$ or $n|b$ (or both) $\Rightarrow [a]=$ or $[b]=$

and I'm stuck on the leftward implication.

Why do I get $[a]=$ OR $[b]=$ and not $[a]=$ AND $[b]=$ in the leftward implication? Where is it that I go wrong?

I'd also appreciate any comment/hint about how to prove the remaining left implication.

• The problem statement is false: $2 \cdot 7 = 0$ in $J_7$ but $2$ is not $0$ in $J_7$. It should be one of the two being zero. – Student Mar 5 '17 at 13:14
• @Student So that's why I got [a]= or [b]=; thank you for bringing up this counterexample. – lorenzo Mar 5 '17 at 13:20
• It would be helpful to add the edition and section or page number from which this exercise is taken. – hardmath Mar 5 '17 at 13:33

## 2 Answers

As I already commented, the problem statement should be:

$n$ is prime if and only if ($[a][b] =  \implies [a] = $ or $[b] = $).

For the leftward direction: Prove this by contraposition: this means that if we want to prove $P \implies Q$, then we do so by proving $\text{not } Q \implies \text{not }P$ (these are equivalent). Hence I will prove the following: If $n$ is not a prime, then we have that $[a][b] = $ and $[a] \neq  \neq [b]$. (since the we have that $\text{not }(K \implies L)$ is equivalent with ($K$ and $\text{not } L$).

First of all, note that $n$ is prime if and only if its only divisors are $1, n$. Hence $n$ is not prime if it has at least one divisor (and then automatically also a second one) which is neither $1$ nor $n$!

Now for your proof:

Suppose $n$ is not prime, then there exists divisors $a,b$ of $n$ which are by definition different from 1 and different form $n$. Hence we can write $n = ab$. In particular, we have that since $1 < a <n$ and $1 < b <n$ that $[a] \neq $ and $[b] \neq $ in $J_n$. However, we have that $$ = [n] = [ab] = [a][b]$$ and this concludes the prove.

• by $c$ and $d$ do you mean $a$ and $b$? If so why should you be able to write $n=cd$? Shouldn't it be $ab=hn$ (where $h\in\mathbb{Z}$) since $[ab]=$ (and thus $n|ab$) or am I getting something wrong about the meaning of congruence class? (see also my comment to the other answer) – lorenzo Mar 5 '17 at 13:59
• @lorenzo yes: I denoted it by $c,d$ in order to prevent you of being confused, but this apparently backfired. I will edit my answer so that I can adress your other questions. – Student Mar 5 '17 at 14:02

Let us prove the leftward implication. That is, we need to show that $$(i)\quad [a][b]= \text{ implies either } [a]= \text{ or } [b]=\qquad\implies\qquad (ii)\quad n\text{ is prime}.$$

We prove this by contradiction. Assume that statement $(i)$ holds and suppose statement $(ii)$ is false. This means that $n$ is not prime, that is, $n$ is composite. Then we write $n=ab$, where $1<a<n$ and $1<b<n$. We know that $$n\equiv 0\pmod n.$$ Thus, $$ab\equiv 0\pmod n.$$ This implies that $[ab]=$. Thus, $[a][b]=$. By hypothesis, either $[a]=$ or $[b]=$. Hence, either $a\equiv 0\pmod n$ or $b\equiv 0\pmod n$. Hence, either $n|a$ or $n|b$ implying that either $n\leq a$ or $n\leq b$. We obtain a contradiction and this proves the result.

• @lorenzo Look at my proof. I assumed that $n$ is composite. What is your definition of a composite? – Juniven Mar 5 '17 at 14:02