## Euclid's Lemma for Prime Numbers

If

\[p\]

is a prime number and divides the product \[N=a_1a_2...a_k\]

then \[p\]

divides one of the factors \[a_1, \; a_2, ,..., a; a_n\]

.Proof

Let

\[P(n)\]

be the statement that if \[n-a_1a_2...a_n\]

then \[p\]

divides one of the factors \[a_1, \; a_2, ,..., \; a_n\]

.\[P(1)\]

is true since if \[p\]

divides \[N=a_1\]

then \[p\]

divides \[a_1\]

/ Suppose that \[P(k)\]

is true for all integers less than or equal to \[n\]

. We must prove \[P(n+1)\]

is true. Let \[N=a_1a_2...a_na_{n+1}\]

. Either \[p\]

divides \[a_{N=1}\]

or it does not. If it does then we are finished. If \[p\]

does not divide \[a_{n+1}\]

then the greatest common divisor or \[p\]

and \[a_{n+1}\]

is 1 and \[p\]

must divide \[a_1a_2...a_n\]

and then \[p\]

divides one of \[a_1, \; a_2,..., \l a_n\]

by the induction hypothesis.If all the factor are prime, then

\[p\]

must be equal to one of these prime factors.