Proof by Induction - Primes and Euclid's Lemma

Feb 2015
5
0
USA
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
Mar 2011
3,546
1,566
Tejas
Try doing induction on the number of prime factors. Start with a base case of 2.
 

chiro

MHF Helper
Sep 2012
6,608
1,263
Australia
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.