1. Suppose a, b, and p are positive integers and p is prime.
Prove that if p|ab, then either p|a or p|b.

I think the easiest is to use proof by contradiction. Suppose it is not true that either p|a or p|b.
Then this means p does not divide a AND p does not divide b.
But if this is the case, then p must not divide ab as well.

However, a more rigorous proof is go by using greatest common divisor. But I could not finish it.

Let d be the greatest common divisor of a and p. Since p is a prime number, then d must be either 1 or p.
If d = p, it follows by the definition of greatest common divisor that p|a. If d = 1,
it follows that p does not divide a. By assumption p|ab.
It should be reasonable to say that if p does not divide b, then p does not divide ab.
But this seems I have returned to proof by contradiction.

2. Suppose $p_1, p_2, ..., p_j$ and $q_1, q_2, ..., q_j$
are two nondecresing sequences of prime numbers, $p_1 \leq p_2 \leq ... \leq p_j$ and
$q_1 \leq q_2 \leq q_k$ and $p_1p_2...p_j = q_1q_2...q_j$
Prove that j = k and $p_i = q_i$ for $1 \leq i \leq j$

I went by induction on j and showing the base case that

$p_1 = q_1q_2...q_k$ which is not possible if k > 1 due to the fact that p is prime.

As for the inductive step, I went by assuming $p_1p_2...p_j = q_1q_2...q_k.$ j = k and $p_i=q_i$ for for $1 \leq i \leq j$ So,

$p_1p_2...p_jp_{j+1} = (q_1q_2...q_k) p_{j+1}$

If for another sequence $q_1q_2q_3...q_k$ must be equal $p_1p_2...p_jp_{j+1}$, and the fact that $p_{j+1} > p_j$, there must be something more to $q_1q_2...q_k$, which is $q_{k+1}$. The inductive hypothesis, j = k and $p_i=q_i$ for for $1 \leq i \leq j$ and the equality $p_1p_2...p_j = q_1q_2...q_k.$ should ensure $p_{j+1} = q_{k+1}$.

However, the right answer seems to be more rigorous but I think mine should be enough. What's wrong with my argument?

2. 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>

3. Originally Posted by Unenlightened
Because , you deduce from Gauss Theorem that . qed
Thanks, but I still do not get it. I think it is similar to my reasoning. What exactly does the Gauss Theorem said?