# 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$.

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

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