Infinity and Beyond

One of the most appealing aspects of proofs is the “wow” factor that some have. Euclid proved the infinitude of primes quite beautifully in my opinion, and this proof is one of my all-time favorites. This can be understood by anyone, and I’m sure anyone who has studied number theory to any depth would have come across it, but for those who haven’t seen it, this proof is something that you should definitely read:

500-prime-numbers.jpg

First 500 primes plotted in a spiral

The proof uses proof by contradiction, and starts out with the assumption that there are a fixed number of primes. Let p be the set of prime numbers, where there are n prime numbers:

Untitled1.png

In that case, consider the number x:

Untitled2.png

Think about the factors that x would have. It turns out that it will have no factors other than itself and 1, which makes it a prime. This is because for it to have any other factor, it needs to divide at least one prime, and x cannot divide any of the primes (1 is not divisible by any of the primes, and therefore 1 added to the product of all primes is prime). You can also think about it as if you were trying to pull out a common factor from this sum, which is not possible, because it will result in a fraction from the 1. Since this number x is also a prime, it gives a contradiction, because we thought we had all the primes in the set p. Therefore the number of primes is infinite. This might well be one of the most beautiful proofs in mathematics.

Advertisements

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