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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.