# Proof by Induction - Primes and Euclid's Lemma

#### erlevesq

Hi guys,

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 q1,q2,...,qs are prime numbers and p divides q1q2...qs, then p=qi 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 a1a2...an, then it must divide at least one of the factors ai. For the inductive step, I can assume p divides q1q2...qs+1 and let a=q1q2...qs. Then, p divides aqs+1 and either p divides a, p divides qs+1, or p=qs+1. I know that since qi is prime, it cannot divide qi unless p=qi 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.

#### Deveno

MHF Hall of Honor
Try doing induction on the number of prime factors. Start with a base case of 2.

#### chiro

MHF Helper
Hey erlevesq.

State the case for some value of i and then state the case for some value of i + 1.

Once you have both see the difference between the two and then combine the two statements.

The difference between i and i + 1 is that you have an extra term. So you have two cases - either it divides into one of the terms in the "ith" case or it doesn't which means it has to divide in the "i+1 th" case.

Write down the algebraic definitions and if you have trouble, please post your working and ideas in this thread.