Euclid's Lemma for Prime Numbers

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.

You have no rights to post comments