Let $p \in \lbrace2,3,4,...\rbrace$. Suppose that for all $x,y \in \mathbb{Z}$, if $p \mid xy$, then $p \mid x \vee p \mid y$. Show that $p$ is prime.

Question

I'm studying for an upcoming exam and came across this question in my textbook. I'm assuming the easiest way to approach this proof is by contradiction. I don't have much so far, I just suppose that $p$ is not prime, but cannot find a way to reach a contradiction from this where $p$ has to be prime based on the fact that $p$ divides $x$ or $p$ divides $y$.

Answer 1

Equivalent to the statement you want to prove is its contrapositive:

If $p$ is not prime, then there are $x,y\in \Bbb Z$ where $p|xy$ but $p$ divides neither $x$ nor $y$.

Try some examples. Take $p=6$ and see if you can find $x,y\in \Bbb Z$ where $6|xy$ but $6$ divides neither $x$ nor $y$. Then try it with $p=8$ and $p=12$. Try to think of a general strategy for finding such $x$ and $y$ once you are given composite $p$. Then ask yourself whether this strategy would work when $p$ is prime. (If the theorem is correct, the strategy shouldn't work.) That should give you some ideas of how to proceed.