So, in the last post we proved that \sqrt{2} is irrational, by trying to see what the consequences would be if it were rational. We first said that if it were rational, then we should be able to write it in a simplest form \frac{p}{q} where p and q had no common factors, and then showed that in fact this was impossible, so our original proposition was indeed true (as trying to prove otherwise gave us a contradiction).
Now we are going to look at another example, which looks very similar, but here our contradiction will be a little different to last time. The fact is that, unlike much of what you would have done at highschool, there isn’t such a roadmap to how to do things here – you have to figure out for yourself where the contradiction comes in. In these posts I will point them out for you, but in general, you need to build your intuition about where something looks a bit dodgy and a contradiction is raising its head.

 

So, let’s try and prove that \sqrt{3} is irrational. We will start with the same game plan and see where we go. We want to show that the converse statement can’t hold. So let’s say: What would happen if \sqrt{3} were rational? If that were the case, then we could write it in a simplest form:

 

\sqrt{3}=\dfrac{p}{q}

 

Where p and q have no common factors (that should certainly be possible if it’s a rational number). OK, again, let’s square both sides and rearrange:

 

3q^2=p^2

 

Hmm, so now it turns out that we don’t have the same reasoning as before, about p^2 being even, so we can’t go down that route. There are two possible routes now. Let’s follow the first which involves using something called The Fundamental Theorem of Arithmetic. This states that:

 

Every integer greater than one is either prime or is a product of primes. Most importantly, it says that this product of primes is unique.

 

What this means is that if I give you a number, you can always decompose it into a product of prime numbers uniquely. For instance 872 can be decomposed into the product:

 

872=2\times 2\times 2\times 109

 

Where 2 and 109 are prime numbers. There are no other ways of writing 872 as a product of primes. Let’s take another random example: 1325:

 

1325=5\times 5\times 53

 

Where 5 and 53 are prime. This fact is actually hugely important for cryptography – the science of hiding information, as used most commonly in internet banking, email systems and many, many other things.

 

Why is this important? Well, if a given number can be written as the product of a certain number of primes,  then that number squared will be written as twice as many primes. For instance. If an integer, a, was 315, then you can write it as:

 

315=5\times 7\times 3\times 3

 

ie as a product of four primes (it doesn’t matter that they’re not all different). But in that case a^2 could be written:

 

315^2=5\times 7\times 3\times 3\times 5\times 7\times 3\times 3

 

Ok, so who cares? Well, this is rather important because it means that a number squared will always be written as the product of an even number of prime numbers (the number above is written as the product of 8 prime numbers). Hmm, so in the above, p^2 can be written as the product of an even number of primes, and so can q^2 for the same reason. But on one side we have an extra number (3). This means that 3 q^2 must be decomposed as an odd number of primes (an even number for q^2 and one more for the 3). On the right hand side, we just have p^2 so this is an even number of primes. So we have that the product of an odd number of primes is equal to the product of even number of primes. However, from the fundamental theorem of arithmetic, we know that any number has a unique prime decomposition, and so you can’t write it in two different ways. This then is our contradiction, we can’t have a number which can be written as the product of both an even number of primes, and as the product of an odd number of primes.

 

There are actually several other ways of proving this same thing without using this fundamental theorem of arithmetic, and which are a bit more like the previous proof for \sqrt{2} but I think that this one is the most elegant. You will find a more similar proof to the last one here.

 

Let’s see again what we did:

  1. We presumed that the original statement was not true
  2. If that were the case it could be written in the form of one integer divided by another where they have no common factors.
  3. Rearranging and using the fundamental theorem of arithmetic we see that one side of the equation has an even number of primes, and the other side has an odd number of primes..
  4. This is impossible and thus we have found a contradiction if we presume that the statement is false.
  5. The statement must therefore be true.

In the next post we will look at another example of proof by contradiction.

 

How clear is this post?