0
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ The converse needs to hold for each $(a, b)$ $\endgroup$ – Peanut Aug 23 '20 at 10:26
  • 2
    $\begingroup$ 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$. $\endgroup$ – Dietrich Burde Aug 23 '20 at 10:26
  • $\begingroup$ See also here for the coprime generalization. $\endgroup$ – Bill Dubuque Aug 23 '20 at 20:51
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I still don't get why it doesn't work for my example, but uses $\forall$ $\endgroup$ – Alexander Kozachenko Aug 23 '20 at 10:46
  • 1
    $\begingroup$ 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. $\endgroup$ – José Carlos Santos Aug 23 '20 at 10:51
  • 1
    $\begingroup$ @AlexanderKozachenko because there exists at least one counterexample that shows $\exists (a,b)(p\mid ab\nRightarrow p\mid a\lor p\mid b)$. $\endgroup$ – justadzr Aug 23 '20 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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