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.

  • $\begingroup$ $$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 $\endgroup$ – 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:

We already have the implication

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

  • $\begingroup$ $p=ab$? – – – – $\endgroup$ – Kenny Lau Jul 30 '16 at 7:41
  • $\begingroup$ @KennyLau reformulated, should be understandable now. $\endgroup$ – Paul K Jul 30 '16 at 7:46
  • $\begingroup$ 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! $\endgroup$ – CoffeeCrow Jul 30 '16 at 8:17
  • $\begingroup$ @CoffeeCrow added a longer version. $\endgroup$ – Paul K Jul 30 '16 at 9:24

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?


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.