# Induction Proof - Primes and Euclid's Lemma

I'm having some trouble with this proof. Here's the question: Use mathematical induction and Euclid's Lemma to prove that for all positive integers $s$, if $p$ and $q_1, q_2, \dotsc, q_s$ are prime numbers and $p$ divides $q_1q_2\dotsb q_s$, then $p=q_i$ for some $i$ with $1 ≤ i ≤ s$.

Here's what I know: Euclid's Lemma says that if $p$ is a prime and $p$ divides $ab$, then $p$ divides $a$ or $p$ divides $b$. More generally, if a prime $p$ divides a product $a_1 a_2 \dotsb a_n$, then it must divide at least one of the factors $a_i$. For the inductive step, I can assume $p$ divides $q_1q_2\dotsb q_{s+1}$ and let $a=q_1q_2\dotsb q_s$. Then, $p$ divides $aq_{s+1}$ and either $p$ divides $a$, $p$ divides $q_{s+1}$, or $p=q_{s+1}$. I know that since $q_i$ is prime, it cannot divide $q_i$ unless $p=q_i$ for some $1 ≤ i ≤ s$. I'm just not sure how to formulate the proof. Usually with Induction I can set some property $P(n)$ and test it is true for some base like $P(0)$ or $P(1)$ for the base step. I'm unsure how to go about it here.

• I would have thought the initial step was to show that if $p$ and $q_1$ are prime and $p$ divides $q_1$ then $p=q_1$. Since $q_1$ is prime, it only has two divisors, namely $1$ and $q_1$; so $p$ must be one of these, and $p$ cannot be $1$ as $1$ is not prime; thus $p=q_1$. – Henry Aug 20 '15 at 23:40
• The "more generally, if a prime divides a product $a_1\cdots a_n$, then $\dots$" is basically what you are being asked to prove. True, it is clear that it is implied by the $a,b$ case, but in principle that extension to $n$ requires induction. – André Nicolas Aug 21 '15 at 0:37

First, we note that $p|q_1$ implies $p=q$ (we don't even need Euclid's lemma to see this).
Now assume that $p|q_1q_2\ldots q_k\implies p|q_1$ or $p|q_2$ or $\cdots$ or $p|q_k$.
Now consider the statement $p|q_1q_2\ldots q_kq_{k+1}$. Using Euclid's lemma, $p$ must divide one of $q_1q_2\ldots q_k$ or $q_{k+1}$. By our inductive hypothesis, we conclude that $p|q_1$ or $p|q_2$ or $\cdots$ or $p|q_k$ or $p|q_{k+1}$.