Let $p>1$ belong to the natural numbers. Assume: if $a$ and $b$ are natural with $p \mid ab$, then $p \mid a$ or $p \mid b.$ Prove that $p$ must be a prime number.

I know how to prove Euclid's lemma assuming $p$ is prime, but I do not know how to prove the title statement without that initial assumption.

  • $\begingroup$ What are you trying to prove (Euclid's lemma or the title statement)? And what is your definition of prime? $\endgroup$
    – pancini
    Oct 8, 2021 at 0:38
  • 1
    $\begingroup$ You may enjoy this math.stackexchange.com/questions/1162373/… $\endgroup$
    – Stan
    Oct 8, 2021 at 0:45
  • $\begingroup$ Im trying to prove the title statement. $\endgroup$ Oct 8, 2021 at 0:56
  • $\begingroup$ Consider $4|4\cdot4$. $\endgroup$ Oct 8, 2021 at 10:29

1 Answer 1


Suppose $p=xy$ for $x,y>1$. Then $p|xy$ but $p\not\mid x$ and $p\not\mid y$.

  • $\begingroup$ Could you please elaborate the explanation? $\endgroup$ Oct 8, 2021 at 0:47
  • $\begingroup$ Which part? It's clear why we can write $p=xy$ and why $p|xy$, right? The other observation is that $1<x<p$, so $x$ can't be a multiple of $p$. $\endgroup$
    – pancini
    Oct 8, 2021 at 1:01
  • $\begingroup$ Thanks it is clear. $\endgroup$ Oct 8, 2021 at 1:05

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