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. 
