The proof that √2 is irrational is five lines long and it still bothers me

Last month I was sitting in the library after a bad mock, too fried for another problem, and I picked up an old maths book somebody had left on the table. It had the proof that $\sqrt{2}$ is irrational. I knew the result from school (it's in the class 10 NCERT), but I'd only memorised it. This time I read it slowly and I think it's one of the best things I've ever seen in maths. So here it is, along with the parts where I got stuck.

The claim

$\sqrt{2}$ cannot be written as a fraction $\dfrac{p}{q}$ of two whole numbers. That's what "irrational" means.

You can't test every fraction, because there are infinitely many. So you don't hunt for the fraction. You assume one exists and see what breaks. That's proof by contradiction.

The proof

Assume $\sqrt{2} = \dfrac{p}{q}$, where $p$ and $q$ are positive integers with no common factor. We can always cancel a fraction down until that's true, and this setup is the important part.

1. Square both sides: $2 = \dfrac{p^2}{q^2}$, so $p^2 = 2q^2$.
2. So $p^2$ is even. If $p$ were odd, $p^2$ would be odd (odd times odd is odd). So $p$ must be even: $p = 2k$ for some integer $k$.
3. Substitute: $(2k)^2 = 2q^2$, so $4k^2 = 2q^2$, so $q^2 = 2k^2$.
4. So $q^2$ is even, and by the same argument as step 2, $q$ is even.
5. Now both $p$ and $q$ are even. They share the factor 2. That contradicts "no common factor".

The assumption led to nonsense, so it was false: $\sqrt{2}$ is irrational. ∎

I stared at it for ten minutes trying to find the trick, and there isn't one. The trick is the very first line, "lowest terms". The contradiction only appears because we insisted the fraction was already fully simplified.

Where I got stuck: why doesn't this prove √4 is irrational?

Try the same steps on $\sqrt{4} = p/q$. You get $p^2 = 4q^2$, which just says $p = 2q$. That's a perfectly fine fraction ($\sqrt{4} = 2/1$) and nothing contradicts anything. The proof for 2 works because $p^2 = 2q^2$ forces both $p$ and $q$ to be even. With 4 you only learn that $p$ is twice $q$.

It generalises, and primes are the reason

For $\sqrt{3}$: $p^2 = 3q^2$, so $3$ divides $p^2$. The key step is that if a prime divides $p^2$, it must divide $p$. This works for primes (it's why the proof is written for 2 and 3 and 5 but we'd need more care for 6 or 10). Then $p = 3k$, so $9k^2 = 3q^2$, so $q^2 = 3k^2$, so $3$ divides $q$ as well. Contradiction again.

The full version: for a positive integer $n$, $\sqrt{n}$ is irrational unless $n$ is a perfect square. The cleanest proof uses prime factorisation: in $p^2 = nq^2$, every prime appears an even number of times on the left side (squares do that), so every prime in $n$ must also appear an even number of times, which means $n$ is a perfect square.

The legend

The story goes that this was discovered in the school of Pythagoras, where the belief was that everything is a ratio of whole numbers, and that the person who proved otherwise was thrown overboard. Historians aren't sure it happened or who the person was, so I treat it as a great story and not a fact. What is solid is that the ancient Greeks knew the diagonal of a square of side 1 has no whole-number ratio with its side. By Pythagoras's theorem that diagonal is $\sqrt{1^2 + 1^2} = \sqrt{2}$. The simplest shape you can draw, and its diagonal is a number no fraction can name.

And in code

>>> import math
>>> math.sqrt(2)
1.4142135623730951
>>> math.sqrt(2) ** 2
2.0000000000000004
>>> 0.1 + 0.2
0.30000000000000004

A computer stores numbers with a finite number of bits, so $\sqrt{2}$ gets rounded to the nearest value it can represent. Squaring that gives something a hair away from 2. (The 0.1 case is different. It's rational, but its binary expansion goes on forever, like 1/3 does in decimal, so it also can't be stored exactly.) Floating point is a polite lie we all agree to live with.

A cute bonus

Can an irrational number raised to an irrational power be rational? Take $x = \sqrt{2}^{\sqrt{2}}$. Either $x$ is rational, in which case we're done with $a = b = \sqrt{2}$. Or $x$ is irrational, in which case take $a = x$ and $b = \sqrt{2}$:

$a^b = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\,2} = 2$

which is rational. Either way the answer is yes, and the proof never even tells us which case is true. (It's actually known that $x$ is irrational, but that needs much heavier machinery to prove.)

I think this is why I like maths. It's one of the only places where you can be completely sure, and it fits on a page.