Prompt: Prove the following by induction on $r$. Suppose $p_1,…,p_r, q_1,…,q_s \in \mathbb{Z}$ are all primes such that $p_1,…,p_r=q_1,…,q_s$. Then $r=s$. (We can use Corollary 1.6: Let $a_1,…,a_m$, $p\in \mathbb{Z}$ with p prime such that $p|a_1,…,a_m$. Then $p|a_i$ for some $i=1,…,m$.)
Below is my Proof Outline, the part I am most struggling with is how to use the fact that the q's are prime to set up a substitution, and figuring out the induction hypothesis.
Proof Outline: Let $p_1,…,p_r, q_1,…,q_s \in \mathbb{Z}$ be primes such that $p_1,…,p_r=q_1,…,q_s$.
Base Case: Let $r=1$. Then $p_1=q_1,…q_s$. Corollary 1.6 applies because this shows $p_1|q_1,…,q_s$. Then Corollary 1.6 tells us that $p_1|q_i$ for some $i=1,…,s$. Note that $q_1,…,q_s$ are prime. Then, (set up a substitution?).
Induction Step: Let $r>1$. Then our Induction Hypothesis is:___. Suppose $p_1,…, p_r,q_1,…,q_s\in\mathbb{Z}$ are primes with $p_1… p_r= q_1…q_2,…,q_s$. Hence, $(p_1,…, p_{r-1}) p_r= q_1,…, q_2,…, q_s$, so __. (Use Corollary 1.6 and a substitution similar to base case to finish.)
Best Answer
Base case (picking where you stoped): if $p_1|q_i$, which is prime, then $p_1=q_i$ and $s=1$.
Induction step: suppose that whenever $p_1 \cdots p_r = q_1 \cdots q_s$, then $r=s$.
Let $p_1 \cdots p_rp_{r+1}=q_1 \cdots q_s$.
Then $p_{r+1}|q_1\cdots q_s$, and by the lemma, $p_{r+1}|q_j$, for some $j$, whence $p_{r+1}=q_j$.
Suppose, without loss of generality, that $j=s$.
Then $p_1 \cdots p_r = q_1 \cdots q_{s-1}$.
By the induction hypothesis $r=s-1$ and therefore $r+1=s$.