# Shorter proof of irrationality of $\sqrt{2}$?

Euclid's proof of the irrationality of $\sqrt{2}$ via contradiction involves arguments about evenness or odness of $a^2 = 2 b^2$ which is then lead to contradiction in using few more steps. I wonder why one needs this line of arguments, isn't it from this expression immediately obvious that all prime factors of both $b^2$ and $a^2$ must have even exponents (and that factor $2^1$ between them makes this impossible)? Is the reason for the "more complicated" structure of the traded proof, that this argument involves implicitly more theory (like the fundamental theorem of arithmetics, maybe)?

• Indeed, the only required ingredient is "an even perfect square is the square of an even number". – Yves Daoust Aug 7 '16 at 12:41
• Of course this proof occurs in Euclid far before anything about prime factorization. – GEdgar Aug 7 '16 at 12:42
• GEdgar: While I believe that the fundamental theorem of arithmetics was'nt appreciated that time, it seems hard to believe that Euclid wasn't aware of the uniqueness of prime factorisation. But maybe this is a gross misconception of the history of maths, of mine... – Rudi_Birnbaum Aug 7 '16 at 12:46
• Euclid himself proved the FTA. But even so, I don't understand how that makes the proof any easier. Why is it obvious that the square root of a prime is irrational? – Elliot G Aug 7 '16 at 12:50
• @ElliotG: by the prime decomposition, $a^2$ and $b^2$ have the factor $2$ with an even multiplicity, so $a^2=2b^2$ (i.e. $2\alpha=2\beta+1$) cannot hold. – Yves Daoust Aug 7 '16 at 12:56

Yes, that is the point - the simple parity-based proof does not require existence and uniqueness of prime factorizations so it can be used before those much deeper results are developed.

It is illuminating to note that the proof based on comparing the parity of powers of two does not need the full uniqueness result but only a much simpler case. Namely, it is easy to prove that every natural can be written uniquely in the form $\, 2^i n\,$ for odd $\,n.\,$ Thus $\, A= 2^{\large J} a,\ B = 2^{\large K} b\,$ for $\,a,b\,$ odd. Therefore $\, A^2\! = 2 B^2$ $\Rightarrow$ $\,2^{\color{#c00}{\large 2J}} a^2 = 2^{\color{#0a0}{\large 1+2K}} b^2.\$ But $\,a,b\,$ odd $\,\color{#f2f}\Rightarrow$ $\,a^2,b^2\,$ odd too, which contradicts uniqueness (LHS has $\rm\color{#c00}{even}$ vs. RHS $\rm\color{#0a0}{odd}$ power of $2).$

To generalize that proof from $\,p = 2\,$ to an arbitrary prime $\,p\,$ would require generalizing the $\,\rm odd^2 = odd\,$ step that we used above,  i.e. we would need to prove $\ p\nmid a,b\,\color{#f2f}\Rightarrow\, p\nmid a^2,b^2.\$ Just as for the case $\,p=2,\,$ for any fixed prime $\,p\,$ we could prove it by a brute-force case analysis. But to prove the result for all primes $\,p\,$ we need something much deeper, e.g. Euclid's lemma $\ p\mid ab\,\Rightarrow\, p\mid a\,$ or $\,p\mid b\$ (or closely related results).

• Yes, this is a clear formulation of what I had in mind in a vague form, thank you very much! – Rudi_Birnbaum Aug 8 '16 at 6:03

Here is one of my favorite proofs for the irrationality of $\sqrt{2}$.

Suppose $\sqrt{2}\in\Bbb Q$. Then there exist an integer $n>0$ such that $n\sqrt{2}\in\Bbb Z$.

Now, let $n$ be the smallest one with this property and take $m=n(\sqrt{2}-1)$. We observe that $m$ has the following properties:

1. $m\in\Bbb Z$
2. $m>0$
3. $m\sqrt{2}\in\Bbb Z$
4. $m<n$

and so we come to a contradiction!

Here is a funny proof of the fact that $\sqrt{m}$ is irrational for non-square $m$. I have seen in it in American Monthly. It is a very cute overkill.

Let $m$ be a non-square integer and suppose that $\sqrt{m}$ is rational, that is, $\sqrt{m}=a/b$ for some coprime integers $a,b$. Well, $mb^2 = a^2$, so $a^2$ is in the ideal generated by $b^2$. However $b^2\neq 1$, so the ideal $b^2\mathbb{Z}$ is contained in some maximal ideal $p\mathbb{Z}$, where $p$ is a prime. Thus, $p|a^2$ and $p|b^2$, that is to say, $p|a$ and $p|b$; a contradiction.

This is a kind of sledge-hammer approach. We consider the Legendre symbol and Dirichlet's theorem.

Since $$\left(\frac2p\right) = (-1)^{\frac{p^2-1}8}= \begin{cases} 1 & \mbox{ if }p \equiv 1\mbox{ or }7 \pmod{8} \\ -1 & \mbox{ if }p \equiv 3\mbox{ or }5 \pmod{8}. \end{cases}$$ Suppose that $\sqrt 2$ is rational, then except for finite number of primes $p$, the polynomial $x^2-2$ is reducible modulo $p$. Then the density of primes $p$ such that $2$ is a quadratic residue mod $p$ becomes $1$.

By the above result on Legendre symbol and Dirichlet's theorem, the density of primes $p$ such that $2$ is a quadratic residue mod $p$ is $1/2$. This is a contradiction.

I think the historical preference for the Euclid-style proof may have something to do with (what I surmise was) how it may have been discovered in the first place.

Suppose you don't know that $\sqrt{2}$ is irrational. Indeed, suppose you don't even know that there are irrational quantities. Like the ancient Pythagoreans, you naively assume that any two magnitudes can be expressed as a ratio in the form $m/n$ where $m$ and $n$ are two natural numbers.

Now you ponder the length of the diagonal of a square. What, you wonder, is the ratio of the diagonal to the side? Well, you assume that ratio is equal to $m/n$ for some $m$ and $n$ with no common factors. How to find the correct values of $m$ and $n$? Do we know anything about how to compare those two segments?

"Ah yes," you suddenly realize, "The square on the diagonal is equal to twice the square on the side!" This is visually obvious (even without knowing the Pythagorean theorem). And this can be used to find out something about $m$ -- namely, that it must be even. And this means that $n$ must be odd. We seem to be making real progress on our quest to find out what $m$ and $n$ are equal to...

...and we are off and running. What seems at first to be a productive avenue of inquiry that might help us figure out what natural numbers have the ratio equal to the ratio of the square's diagonal to its side instead leads us to a reductio ad absurdum.