# Thread: Euclid's Lemma Proof by Induction

1. ## Euclid's Lemma Proof by Induction

Hi,

I was hoping you could help me prove Euclid's lemma using induction. I want to show by induction that if a prime p, divides a product of n numbers, then it divides at least one of the numbers.

I've attempted this myself but what I attempted did not make sense to me. I tried taking the approach that if p|a1a2...an then looking at the case n=1 if p|a1 then we're done by hypothesis and that didn't seem right to me because I kept going in a loop. Help!

Hi,

I was hoping you could help me prove Euclid's lemma using induction. I want to show by induction that if a prime p, divides a product of n numbers, then it divides at least one of the numbers.

I've attempted this myself but what I attempted did not make sense to me. I tried taking the approach that if p|a1a2...an then looking at the case n=1 if p|a1 then we're done by hypothesis and that didn't seem right to me because I kept going in a loop. Help!
$P(1): \ p|a \ \text{true}$

$P(k): \ p|(a_1a_2\cdots a_k)$

Assume true for a fixed but arbitrary value k such that $n\leq k$

$P(k+1): \ p|(a_1a_2\cdots a_ka_{k+1})$

By using P(k), prove P(k+1) is true.

3. The main difficulty here is when n = 2. This is where one has to use the fact that p is prime. This has to be proved separately. After that proving it for arbitrary n by induction is pretty simple, as described above.