I'm reading a book about proofs and fundamentals on my own and, currently, I'm having trouble proving this result.
Theorem: Let $p$ be a positive integer bigger than or equal to $2$ and such that, for any integers $a$ and $b$, if $p|ab$, then $p|a$ or $p|b$. Show that $p$ is a prime number.
Sketch Work: My work so long has been assuming that $p$, in this condition, is a composite number. Hence, there exists some integers $m$ and $n$, such that $p = mn$ and $1 < m,n < p$. If $p|ab$, then there is some integer $k$ such that $kp = ab$. How do I show from here that $p$ will not divide $a$ and $b$ and hence we have a contradiction?
Is my strategy good? What should be the next step? Thank you!
Best Answer
If $p$ is composite, then $p=mn$ where $1<m,n<p.$ We have $p \mid mn,$ so by assumption $p\mid m$ or $p \mid n$ which is a contradiction since $m,n<p.$
Edit: The hypothesis says that if $p \mid ab,$ then $p \mid a$ or $p \mid b.$ In order to use this, you need to find integers $a$ and $b$ such that $p \mid ab.$ The hypothesis does not say that there definitely exist such integers. Assuming that the conclusion does not hold guarantees such existence and then puts you in a position where you can use the hypothesis.