# The converse of Euclid's Lemma

Im having trouble proving the converse of Euclid's lemma, and was wondering if anyone could point me in the right direction.

Euclid's Lemma: Let $p$ be a prime number and $a$ and $b$ be natural numbers greater than 1, then if $p|ab$ we know $p|a$ or $p|b$

Converse: For some number $p$, if for all natural numbers $a$ and $b$ greater than 1, $p|ab$ implies $p|a$ or $p|b$, then $p$ is prime.

I tried showing that $p$ had only factors 1 and $p$, but I didn't really manage to make any progress, I'm just really not sure where to start, I'd really appreciate any help, thanks.

• $$p^aq^b$$ divides $p^{a+1}q^{b+1}r^{c+1}\cdots$ $$p^aq^b$$ divides $$p^{a+1}q^{b+1}$$ and not $$r^{c+1}\cdots$$ where $p,q,r$ are co-primes – lab bhattacharjee Jul 30 '16 at 7:32

If $p$ is not prime, then there are $a,b \neq p$ with $p = ab$. Now $p \mid ab$ but $p \not \mid a, p \not \mid b$.

longer version:

($p$ prime) $\implies$ (if $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$)

We want to show the implication

(if $p \mid a \cdot b$, then $p \mid a$ or $p \mid b$) $\implies$ ($p$ prime)

We do this my contraposition:

($p$ not prime) $\implies$ (there exist $a,b$ with $p \mid a \cdot b$ and $p \not \mid a, p \not \mid b$)

Now, if $p$ is not prime, then there is a factorization $p = a \cdot b$ with $a \neq p \neq b$. Hence we have $p \mid a \cdot b$, but $p \not \mid a, p \not \mid b$, which shows the above implication.

• $p=ab$? – – – – – Kenny Lau Jul 30 '16 at 7:41
• @KennyLau reformulated, should be understandable now. – Paul K Jul 30 '16 at 7:46
• Im sorry, I'm still pretty new to proof writing in general, so I'm not 100% sure if I follow and would like to check my understanding. My understanding is this is a proof by contradiction. You assume p isn't prime, recognize it must then be composite, then obviously p=1*ab so p|ab, but p then can't divide a or b, so this is a contradiction, thus p is prime, is this right? Thanks for your help by the way! – CoffeeCrow Jul 30 '16 at 8:17
• @CoffeeCrow added a longer version. – Paul K Jul 30 '16 at 9:24
• Can you explain why $p \not \mid a, p \not \mid b$ . Is it because by substitution $a \cdot b \not \mid a$ and $a \cdot b \not \mid b$ ? Though for this to hold we would have to know that $a, b \neq 1$ (we would have to show that in $p = a\cdot b$ , it is the case that $a,b \neq 1$ ) – john Jan 12 at 17:28

Suppose $p=ab$. By assumption, either $p\mid a$ or $p\mid b$.

If $p\mid a$, then $a=pc$, for some $c$ and so $$a=pc=abc$$ Since $a\ne0$, we get $bc=1$. Can you go on?

• I don't see how this proves the converse. – john Feb 7 at 10:34
• @john We have to prove that either $a=p$ or $b=p$. In the case $p\mid a$, we get $bc=1$, so $b=c=1$ and so $p=a$. Similarly if $p\mid b$. – egreg Feb 7 at 10:42

By assumption, $$p|ab$$ and either $$p|a$$ or $$p|b$$. Let $$ab = p_{1}p_{2}\cdots p_{n}$$ be the prime decomposition of $$ab$$. We know that $$p|ab$$ and so, $$p|p_{1}p_{2}\cdots p_{n}$$. Then $$p$$ must divide one of $$p_{i}$$ for $$1 \leq i \leq n$$. Since $$p_{i}$$ are primes, it follows that $$p$$ must be prime.