Thread: 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!

Originally Posted by mrspotatohead

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!

Assume true for a fixed but arbitrary value k such that



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

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.