Oct
29
2009

How do we know that there are an infinite number of prime numbers?

The first 500 primes, plotted in a spiral (image by modern_carpentry - CC-BY)

The first 500 primes, plotted in a spiral (image by modern_carpentry - CC-BY)

REFINANCEHOMEMORTGAGEE.COM

A prime number is any number that can be divided only by itself and one. For example, 7 and 11 are prime numbers, but 12 is non-prime (because it can be divided by 2, 3, 4 and 6 in addition to itself and one).

Around 300 BCE, Euclid deduced that there must be an infinite number of primes. He used a clever construction to prove this. His argument went like this:

  • If the number of primes is not infinite, then there must be a limited number of primes
  • But, starting from this list of primes, I can show a way to generate another prime number
  • Therefore there cannot be a limited number of primes.

Euclid's proof works like this:

  • Start with a list of all the primes that you know about so far
  • Multiply them all together and add one, to produce a new number not on the list

This new number must be either prime or composite (nonprime). If it is prime, we have a new prime number, not already on our list. If our new number is not prime, it must be divisible by some prime factor. But that prime factor can't already be on our list of primes (because those primes are all divisors of the number one less than our new number). So that prime factor must be a new prime number, not already on our list.

Either way, we have added one more prime number to our list of primes. We can apply the same process over and over again, generating a new prime number each time. Therefore the number of primes is infinite.

The statement that there are infinitely many primes is called Euclid's theorem. Other mathematicians, including Euler, have formulated alternative proofs of the infiniteness of primes.

zp8497586rq
zp8497586rq

Related questions:

  Need research? Quezi's researchers can answer your questions at uclue.com

Written by | 5,966 views | Tags: , , , ,

2 Comments

  • david says:

    I wish someone would explain that spiral plot to me. I don’t get it at all! Chip…where are you?

  • mvguy says:

    I would have thought that a mathematical proof of “there are an infinite number of prime numbers” would be a challenge to understand. But that was easy. Maybe I’ll try Fermat’s last theorem next.

RSS feed for comments on this post.


Privacy Policy | Acknowledgements