Infinity of primes

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

Solution.

Assume to the contrary a finite set of primes \{p_1, p_2, ..., p_k\}. \ldots (1).

Consider n = p_1 \times p_2 \times ... \times p_k + 1.

Now, p_i | n-1 \forall 1 \leq i \leq k .

\therefore n is not a multiple of any prime from the assumed finite set.

Hence, n satisfies the definition of a prime number (i.e. one which is not a multiple of primes strictly smaller than itself.)\ldots (2).

(1) and (2), implies contradiction.

 

Q.2. Prove that there are infinitely many primes of the form 4n -1.

Solution.

Claim. A number of the form 4n-1 always has a prime factor of the form 4n-1.

Proof of claim.

Consider any k = 4n-1.

If k is prime, we are done.

Else, k = k_1. k_2, where k_1 \equiv 1 (mod 4) and k_2 \equiv 3 (mod 4). (verify!)

If k_2 is prime, we are done. Else, proceed as above.

The process concludes (if it does not find a greater prime of the form 4n-1) at 3.

Hence, the claim is proved.

-

Assume there are only a finite number of primes of the form 4n-1. Their product is either of the form 4n-1 or 4n+1. Add either 4 or 2, as the case may be, to obtain the next number, call it p, of the form 4n-1.

Now, p is not a multiple of any of the primes from the assumed finite set, contradicting the statement of the claim.

-

 

 

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: