# Infinity of primes

October 7, 2010 Leave a comment

Q.1. Prove that there are infinitely many primes.

Solution.

Assume to the contrary a finite set of primes . .

Consider .

Now, .

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 .

Solution.

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.