# The converse of Euclid's lemma when number isn't prime

Euclid's lemma $$\forall p[Prime(p) \rightarrow \forall (a, b) [p|ab \rightarrow p|a \lor p|b]]$$ Converse $$\forall p[\forall (a, b) [p|ab \rightarrow p|a \lor p|b] \rightarrow Prime(p)]$$ The proof here makes sense to me. I can't grasp how do concrete examples like p = 9, a = 18, b = 9 fit here?

• The converse needs to hold for each $(a, b)$ – Peanut Aug 23 '20 at 10:26
• It says for all $a,b$. So better take $a=6$ and $b=3$ with $p=9$. Then $p\mid ab$ but neither $p\mid a$ nor $p\mid b$. – Dietrich Burde Aug 23 '20 at 10:26
• See also here for the coprime generalization. – Bill Dubuque Aug 23 '20 at 20:51

## 1 Answer

The assertion here is this: given a natural number $$p$$, if for every pair $$(a,b)$$ of natural numbers, when $$p\mid ab$$, then $$p\mid a$$ or $$p\mid b$$, then $$p$$ is prime. Note the presence of the word “every”. So, indeed, if $$p=b=9$$ and $$a=18$$, you do have $$p\mid ab\implies p\mid a\vee p\mid b$$. And indeed $$9$$ is not a prime number. However, $$(18,9)$$ is just one pair of natural numbers. And $$9$$ is not prime because, for instance, $$9\mid3\times6$$, but $$9\nmid3$$ and $$9\nmid6$$.

• I still don't get why it doesn't work for my example, but uses $\forall$ – Alexander Kozachenko Aug 23 '20 at 10:46
• A single example will not do. Yes, $9\mid18\times\implies9\mid18\vee9\mid9$. No problem here. But is it true that for every pair $(a,b)$ of natural numbers you have $9\mid ab\implies9\mid a\vee9\mid b$? Not, as I have shown in my answer. – José Carlos Santos Aug 23 '20 at 10:51
• @AlexanderKozachenko because there exists at least one counterexample that shows $\exists (a,b)(p\mid ab\nRightarrow p\mid a\lor p\mid b)$. – justadzr Aug 23 '20 at 10:53