1. Supposea, b,andpare positive integers andpis prime.

Prove that ifp|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$\displaystyle p_1, p_2, ..., p_j$ and $\displaystyle q_1, q_2, ..., q_j$

are two nondecresing sequences of prime numbers, $\displaystyle p_1 \leq p_2 \leq ... \leq p_j$ and

$\displaystyle q_1 \leq q_2 \leq q_k$ and $\displaystyle p_1p_2...p_j = q_1q_2...q_j$

Prove that j = k and $\displaystyle p_i = q_i$ for $\displaystyle 1 \leq i \leq j$

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

$\displaystyle 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 $\displaystyle p_1p_2...p_j = q_1q_2...q_k.$ j = k and $\displaystyle p_i=q_i$ for for $\displaystyle 1 \leq i \leq j$ So,

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

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