Proof That the Set of Prime Numbers is Infinite

Theorem: There are infinitely many prime numbers.

Proof: Suppose, contrary to the theorem, that there is only a finite number of primes. Thus, there will be a largest which we can call p. Now define a number n as 1 plus the product of all the primes:

n = (2 X 3 X 5 X 7 X 11 X...X p) 1

Is n itself prime or composite? If it is prime then our original supposition is false, since n is larger than the supposed largest prime p. So now let’s consider it composite. This means that it must be divisible (without remainder) by prime numbers. However, none of the primes up to p will divide n (since we would always have remainder 1), so any number which does divide n must be greater than p. This means that there is a prime number greater than p after all. Thus, whether n is prime or composite, our supposition that there is a largest prime number is false. Therefore, the set of prime numbers is infinite.


There is always one larger.

Folksonomies: mathematics theorem prime numbers proof

/science/mathematics/arithmetic (0.706196)
/science/computer science/cryptography (0.472902)
/religion and spirituality (0.447503)

prime numbers (0.998950 (negative:-0.411190)), largest prime number (0.774657 (negative:-0.421883)), primes (0.683002 (negative:-0.196899)), original supposition (0.656978 (negative:-0.221876)), finite number (0.612381 (negative:-0.349956)), theorem (0.577841 (negative:-0.521906)), Proof (0.571470 (negative:-0.469031)), remainder (0.563827 (neutral:0.000000)), set (0.541033 (neutral:0.000000)), Infinite (0.466623 (neutral:0.000000))

Prime number (0.963249): dbpedia | freebase | opencyc
Mathematics (0.868397): dbpedia | freebase | opencyc
Natural number (0.680306): dbpedia | freebase | opencyc
Prime numbers (0.570217): dbpedia
Mersenne prime (0.569674): dbpedia | freebase | yago
Number theory (0.521586): dbpedia | freebase | opencyc
Great Internet Mersenne Prime Search (0.505930): dbpedia | freebase | yago
Largest known prime number (0.487893): dbpedia | freebase

 Philosophy of Mathematics
Books, Brochures, and Chapters>Book:  Brown, James Robert (2012-10-12), Philosophy of Mathematics, Routledge, Retrieved on 2013-06-18
  • Source Material []
  • Folksonomies: mathematics philosophy