How to go about proving that $p$ is prime? 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.
 A: 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$?
A: 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.
A: If $p$ is not prime, write $p=rs$...  Then $p|rs$, but $p\not|r \text { and } p\not|s$ 
