One of my first adventures into formal proof-based mathematics was a proof that the square root of 2 is irrational, that is, can not be expressed in the form where and are integers.
It didn’t feel good at the time. Many readers are likely familiar with it but let’s delve into the details (before we present another [better?] proof).
Proof. Assume that we can write where and are integers with no factors in common other than one.
Then we can square both sides and rearrange to get
From the above, we see that is even. It follows that must also be even and so we can write where is an integer.
Substituting this into the above equation yields
which further simplifies to
Therefore, is even and so must also be even.
Thus, we have shown that and are both even, but this is a contradiction as we assumed that they have no factors in common.
I’m not sure why it didn’t sit with me particularly well. It seemed to me like we made an assumption that had very little to do with the square root of 2 itself. I can’t really put my finger on it.
Theodor Estermann provided a nicer proof with a contradiction that feels slightly better to me. Harley Flanders generalised the argument to where is not a square number. We present his proof as follows:
Proof. We let denote the integer part of , that is, is the integer satisfying
We will prove that is irrational as it follows then that is irrational.
Let’s assume that is rational. Then we may write it as
where and the denominator is as small as possible. This is fine to assume, as given all of the rational representations of there must be one with the smallest possible denominator (see the well-ordering principle).
Then, we have that
We do the high-schooler thing and multiply the top and bottom of this fraction by to get
We can also recover the number of interest, in the numerator of this new fraction:
Now, we can rearrange for . Doing this gives us that (try it yourself!):
This is a contradiction as we assumed that was the smallest possible denominator, but here we have found a fraction with as the denominator, and we know that .