Prove that if p divides xy then p divides x or p divides y I am given that the following proposition is true. (Proved in class)
"Suppose that $x$, $y\in \Bbb Z$, not both zero. Then there exists $m$, $n\in\Bbb Z$ such that $$mx + ny = d$$ where $d$ is the greatest common factor of $x$ and $y$.  Moreover, if $ax + by = f$ for some $a$, $b$, $f\in\Bbb Z$ then $d | f$."
Using the statement above, prove that if $p$ is prime and $p|xy$ then $p|x$ or $p|y$. (hint: if $p$ does not divide $x$, then $p$ and $x$ are relatively prime)(We just learned the definition of  relatively prime, so that is probably why that hint is there.)
I just don't get why I need to use the statement above.  The way I see it, if $p|xy$ then there are two possible cases:


*

*$p|x$

*$p$ does not divide $x$


And obviously, if $p|x$ then the original statement is true, and if $p$ does not divide $x$ then I just need to prove that $p|y$ in that case which I could do.  That seems simpler than any other way, am I wrong?  Working with prime numbers always throws me.  I don't get why it matters if $p$ is prime, so if someone wants to explain that, it would be a nice addition.

If $p$ is not prime, the following thing is posssible:

$p|xy$, however $p$ does not divide $x$ and $y$. 

For example, 8|2\times 4, however $8\not| 2 $ and $8\not| 4 $.
