# Thread: Euclid's lemma and induction

1. ## Euclid's lemma and induction

Use Euclid's Lemma and induction to prove that if p and
q1,q2,q3,...,qn (1,2,3 and n are subscripts) are prime numbers
and p divides q1q2q3...qn ( the product), then p=qi for some
i=1,2,3....n.

2. Originally Posted by JCIR
Use Euclid's Lemma and induction to prove that if p and
q1,q2,q3,...,qn (1,2,3 and n are subscripts) are prime numbers
and p divides q1q2q3...qn ( the product), then p=qi for some
i=1,2,3....n.
Euclid's lemma tells you that this is true for $\displaystyle n=2$.

Now suppose it true for some $\displaystyle n=k$, then we have for any prime numbers:

$\displaystyle p, q_1, .., q_{k+1}$

Then by Euclids lemma if $\displaystyle p | q_1q_2...q_{k+1}$ then either $\displaystyle p|q_1q_2...q_{k}$ or $\displaystyle p|q_{k+1}$. But we already have by assumption that if $\displaystyle p|q_1q_2...q_{k}$ then $\displaystyle p$ divides one of $\displaystyle p_1, ...,p_k.$ Hence the result if true for $\displaystyle n=k$ is true for $\displaystyle n=k+1$, and with the base case we have a proof by induction for all integers $\displaystyle n \in \{2,..\}.$

RonL