# A proof that $\sqrt{2}$ is not a rational number.

Is this proof correct?

Suppose that $$\sqrt{2}=\frac{a}{b}$$, where $$a,b \in \mathbb{N}$$ and $$a$$ is as small as possible. Then $$\sqrt{2}b=a$$ which means $$2b=\sqrt{2} a$$. So we rewrite $$\sqrt{2}=\frac{a}{b}\cdot\frac{\sqrt{2}-1}{\sqrt{2}-1}=\frac{\sqrt{2}a-a}{\sqrt{2}b-b}=\frac{2b-a}{a-b}.\,$$ Note $$\,2b-a=a(\sqrt{2}-1). So this fraction has a smaller numerator than the one we had. So this is a contradiction.

• Yes, this is a well-known proof. Dec 8, 2018 at 13:15
• @user42493 This is essentially the same as this section with $a=m$, $b=n$, $k=2$, $q=1$. At least you were creative enough to 'discover' another proof. Dec 8, 2018 at 13:18
• Note that $2b-a<a$ is equivalent to $2b<2a$, which is true because $a>b$. Dec 8, 2018 at 13:57

It's a well-known proof. Essentially it uses denominator descent by the division algorithm, though that is greatly obfuscated . Below I clarify this viewpoint for the generalization below. The proof in the question is exactly the special case $$\, k = 2\,$$ and $$\,q = \lfloor \sqrt 2\rfloor = 1\,$$ in the proof below.

Irrationality of $$\sqrt k\,$$ if it is not an integer (excerpted from Wikipedia, slightly edited)

For an integer $$k>0$$, suppose $$\sqrt k$$ is not an integer, but is rational and can be expressed as $$\frac{a}b$$ for natural numbers $$a$$ and $$b$$, and let $$q$$ be the largest integer no greater than $$\sqrt k.\,$$ Then

\begin{aligned}{\sqrt {k}}&={\frac {a}{b}}\\[8pt]&={\frac {a({\sqrt {k}}-q)}{b({\sqrt {k}}-q)}}\\[8pt]&={\frac {a{\sqrt {k}}-aq}{b{\sqrt {k}}-bq}}\\[8pt]&={\frac {(b{\sqrt {k}}){\sqrt {k}}-aq}{b({\frac {a}{b}})-bq}}\\[8pt]&={\frac {bk-aq}{\color{#c00}{a-bq}}}\end{aligned}

The numerator and denominator were each multiplied by $$(\sqrt k − q)\,$$ — which is positive but less than $$1$$ and then simplified independently. So the two resulting products, say $$a'$$ and $$b'$$, are themselves integers, which are less than $$a$$ and $$b$$ respectively. Therefore, no matter what natural numbers $$a$$ and $$b$$ are used to express $$\sqrt k$$, there exist smaller natural numbers $$a' < a$$ and $$b' < b$$ that have the same ratio. But infinite descent on the natural numbers is impossible, so this disproves the original assumption that $$\sqrt k$$ could be expressed as a ratio of natural numbers.

We can rewrite the above proof much more conceptually as below, where "$$n\,$$ is a denom of $$\,r$$" means that the rational $$\,r\,$$ is writable with denominator $$\,n,\,$$ i.e. $$\,n\,r = j\,$$ for some integer $$\,j.$$

\begin{align} [\!\!]\qquad\quad\:\!\ \ b \sqrt k\, &=\, a\qquad\ \, \Rightarrow \text{\,b\ is a denom of }\:\! \sqrt k\\ \sqrt k\,\cdot\, [\!\!]\ \ \, \Rightarrow\,[\!\!]\qquad\quad\ \ a\sqrt k\, &=\, bk\qquad \Rightarrow \text{ a\, is a denom of }\:\! \sqrt k\\ [\!\!] - [\!\!]q\,\Rightarrow\,[\!\!] \ \ \ \, (\color{#c00}{a\!-\!bq})\sqrt k\, &=\, bk\!-\!aq\,\Rightarrow\, \color{#c00}{\bar a} \, \text{ is a denom of \:\!\sqrt k,\,\ \color{#c00}{\bar a := a\bmod b}}\\ \end{align}\quad

If $$\,b\,$$ doesn't divide $$\,a\,$$ we get a smaller denom $$\, 0 < \color{#c00}{a \bmod b} < b\,$$ so infinite descent (on denoms), contra $$\Bbb N\,$$ is well-ordered. Hence $$\,b\,$$ divides $$\,a,\,$$ so $$\,\sqrt k = a/b = n\in \Bbb Z,\,$$ so $$\,k = n^2$$.

Alternatively we can use the minimal criminal form of descent: assume that $$\,b\,$$ is the least denominator then deduce a contradiction that a smaller denominator exists if $$\,b\,$$ doesn't divide $$\,a$$.

The denominator descent ($$a,b$$ denoms $$\Rightarrow a\bmod b\,$$ denom) can also be performed by taking fractional parts of equivalent fractions (a form favored by John Conway).

This method generalizes to show the $$\,\Bbb Z\,$$ (or any PID) is integrally-closed, i.e. no proper fraction is a root of a polynomial that is monic (lead coef $$= 1),\,$$ i.e. the monic case of the Rational Root Test. You can find much further discussion of this and related ideas in my posts on denominator ideals.