How to go about proving that $p$ is prime?

Question

Let $p\in\{2,3,4,\dots\}$. Suppose that $\forall x,y\in\mathbb Z\ p\mid xy\implies p\mid x\lor p\mid y$. Show that $p$ is prime.

I am not fully understanding this problem. If I input numbers into the equation so for example $x = 5, y = 10$ and $p = 10$ then $p$ is clearly not prime, but it does divide the product of 5 and 10. Am I suppose to assume that $p$ is prime? if that's the case why do I have to show that $p$ is prime? Thanks.

Answer 1

Let's unpack "$\forall x,y\in\mathbb{Z}, p\mid xy\implies p\mid x\lor p\mid y$" a little.

This says,

• First write down all possible pairs $(x,y)$ where $x$ and $y$ are both in $\mathbb{Z}$.
• Now throw most of them away, keeping only the ones where $p \mid xy$.
• Of the surviving pairs, are any a witness to the falsehood of "$p\mid xy\implies p\mid x\lor p\mid y$"? To be such a witness, we must have a pair $(x,y)$ that makes "$p\mid xy$" true (which we've arranged by throwing out the pairs that do not do so) while also making "$p\mid x\lor p\mid y$" false.

You are to show that the absence of witnesses to falsehood forces that $p$ is prime. Equivalently, by contraposition, you are to show that $p$ not a prime forces the existence of a witness of falsehood.

Working through a simple example can suggest an outline of the proof. As an example of showing the contrapositive version, the choice $p=6$ is not prime. Now take $x = 2$, $y=3$. We see that $p = 6 \mid 6 = 2 \cdot 3 = x y$. However, $p = 6 \not\mid 2 = x$ and $p \not\mid 3 = y$. Consequently, the pair $(2,3)$ is a witness to the falsehood of the implication when $p = 6$. So for this particular choice of not prime $p$, we have shown that there is a witness to falsehood of the implication. How would you modify this argument to work for an arbitrary not prime $p$?

Answer 2

Do it by induction on the number of primes dividing $xy$.

If two primes divide $xy$, then one must be $x$ and the other must be $y$. Since $p$ divides one of these, it is prime.

If $n+1$ primes divide $xy$, then both $x$ and $y$ have at most $n$ primes dividing them. By the induction hypothesis, whichever $p$ divides forces $p$ to be prime.

Answer 3

If $p$ is not prime, write $p=rs$... Then $p|rs$, but $p\not|r \text { and } p\not|s$