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$ – user301452 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$ – user301452 Jul 30 '16 at 9:24
  • $\begingroup$ 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 $ ) $\endgroup$ – john Jan 12 '20 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?

  • $\begingroup$ I don't see how this proves the converse. $\endgroup$ – john Feb 7 '20 at 10:34
  • $\begingroup$ @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$. $\endgroup$ – egreg Feb 7 '20 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.


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.