Short sweet and simple proofs.

I really want to talk about graph theory at some point, but I don’t know how to make nice graphs in Latex so that may be a while. Instead while fumbling around trying to think of something good to talk about I decided upon some classic short easy proofs.

There are an infinite number of prime numbers.

I see an awful lot of bad attempts at justifying this statement on Reddit. Some people say, “well since there are an infinite number of regular numbers, there must be an infinite number of primes.” This makes about as much sense as saying, “well since there are an infinite number of regular numbers, there are an infinite number of 5’s.” There is only one 5, and it is 5.

First remember that a prime number is a number that has as divisors only 1 and itself. That is, no other number divides into a prime number “nicely.” For some reason mathematicians don’t include 1 to be prime, so instead the list starts off with 2,3,5,7,11,13… and so on possibly forever. 9 is not a prime because 3 divides into it, while 11 is a prime because only 1 and 11 go into it. Another way of saying this is that it doesn’t factor into any other numbers.

Primes also build up all other numbers because any number can be factored into primes.

To begin the proof I am again going to pretend that the statement is false and show that this leads to a contradiction, proving that the statement must be true instead.

Suppose that there is not an infinite number of prime numbers. Since there is not an infinite number of prime numbers, there must instead be a finite amount. So I can make a finite list of ALL the primes that exist. Let the following be that list:
\{p_{1},p_{2},p_{3},\ldots,p_{n}\} .
I can multiply all of these primes together and then add 1 to get a new number P.
P = p_{1}\cdot  p_{2}\cdot  p_{3}\cdot \ldots  p_{n} + 1
Adding 1 is the key to this. Since P is a number, I have to be able to factor it into primes, which is where we run into a problem. We listed ALL of the primes above, but none of these divide the new number that I just created. Here’s why.
Say that I have a number p that does divide P. If p was in the previous list then it would divide all of the numbers in the list being multiplied together;
p \text{ divides } p_{1}\cdot  p_{2}\cdot  p_{3}\cdot \ldots  p_{n}
So then we have that
p \text{ divides } P and that
p \text { divides } p_{1}\cdot  p_{2}\cdot  p_{3}\cdot \ldots  p_{n}
Because of this we have that
p \text{ divides } P - p_{1}\cdot  p_{2}\cdot  p_{3}\cdot \ldots  p_{n}
But P - p_{1}\cdot  p_{2}\cdot  p_{3}\cdot \ldots  p_{n} = 1
which would mean that p also divides 1, but that is impossible unless p = 1 which is not a prime in the list.
Therefore the original list did NOT contain all possible primes so then there are actually an infinite number of prime numbers since our assumption created a contradiction.

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

One Response to Short sweet and simple proofs.

  1. Pingback: Is Math the same on other planets? |

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