Suppose a, b, and p are positive integers and p is prime.
Prove that if p|ab, then either p|a or p|b.
<stolen from Laurent elsewhere on MHF>
It results from Gauss Theorem: We assume that . If , we are done. Suppose . Then and are relatively prime.
(If divides and , then or because is prime, hence necessarily since ; hence is the only positive common divisor of and )
Because , you deduce from Gauss Theorem that . qed
</stolen from Laurent elsewhere on MHF>