Home > Discrete Mathematics > How many primes are there?

How many primes are there?

Prime number is a natural number greater than 1 and has exactly 2 divisors, 1 and itself.

The first few prime numbers are 2, 3, 5, 7, 11, 13, 17 …

The question is, How many primes are there? or in other words, is there a finite number of primes?

The answer is NO, there are infinite number of primes and we are going to prove this below together.

Proof

This is another clever proof by contradiction.

If you believe that there are infinite number of primes, I’ll ask you to write them all in ascending order. I’ll then convince you that you have missed one or more primes which is a contradiction to what you have just claimed and thus the number of primes is NOT finite (infinite).

First let’s first do some brainstorming on some basic concepts.

  • Is 35 divisible by 2? – No because 35 is odd and the division by 2 yields a remainder of 1.
  • Is 6×126+1 divisible by 2?- No, because 6×126 is even and there’s 1 left over after division.
  • Is 3×75+1 divisible by 3? – No, there would be 2  left over after division.
  • Is 3×75+2 divisible by 3? – No, there would be 1  left over after division.
  • Is 3×75+6 divisible by 3? – Yes, 3×75 is divisible by 3 and 6 is divisive by 3 too.

OK. Now back to our proof.

Assumption: Let’s claim that the number of primes is finite and the largest one is 13, we can then write them all as below:

2, 3, 5, 7, 11, 13.

So these are all the primes and any number should be a composite of these numbers, for example (4=2×2, 30=2x3x5, …)

Now I am asking you, What about the following number (2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031)

  • Is (2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031) divisible by 2? – No there would be 1 left over after division.
  • Is (2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031) divisible by 3? – No there would be 1 left over after division.
  • Is (2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031) divisible by 5? – No there would be 1 left over after division.
  • .
  • .
  • Actually this number is not divisible by any of the primes you suggested.

So what does that mean? Does it mean that this number (30031) must be itself another prime?

No, There are two possibilities here:

  1. This number (30031) might be itself a prime which contradicts to your assumption that you have got all primes (finite number of them) where 13 was the last prime and this contradiction implies that the number of primes are not finite as you claimed (We have got a new one here! ;)).
  2. This number is not prime and it has some other prime factor(s) that was not included in the list of all primes you suggested above. This also contradicts to your assumption that you could get all primes  (because you have just missed one or more of them ! 😉 ) and this also implies that the number of primes is infinite.

To summarize, both possibilities above implies that you have missed one or more primes with your assumption. While your assumption claims that there are finite number of primes and I could, from your assumption, prove that you have missed one or more primes then we have a CONTRADICTION case that proves the opposite of your assumption which is “There are infinite number of primes“.

Historical notes:

  • Euclid proved this around 300 BC in his Elements.
  • GIMPS, The Great Internet Mersenne Prime Search (GIMPS) is a collaborative project of volunteers who use Prime95 and MPrime computer software in order to search for Mersenne prime numbers.
  • The largest known prime number ( (243,112,609 − 1) whic is about 12.9 million digits, Aug 08 ) is a Mersenne prime.
Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: