Infinity of primes
October 7, 2010 Leave a comment
Q.1. Prove that there are infinitely many primes.
Assume to the contrary a finite set of primes . .
is not a multiple of any prime from the assumed finite set.
Hence, satisfies the definition of a prime number (i.e. one which is not a multiple of primes strictly smaller than itself.).
(1) and (2), implies contradiction.
Q.2. Prove that there are infinitely many primes of the form .
Claim. A number of the form always has a prime factor of the form .
Proof of claim.
Consider any .
If is prime, we are done.
Else, , where and . (verify!)
If is prime, we are done. Else, proceed as above.
The process concludes (if it does not find a greater prime of the form ) at 3.
Hence, the claim is proved.
Assume there are only a finite number of primes of the form . Their product is either of the form or . Add either or , as the case may be, to obtain the next number, call it , of the form .
Now, is not a multiple of any of the primes from the assumed finite set, contradicting the statement of the claim.