Square roots proved irrational by denominator descent

Question

Is this proof correct?

Suppose that $\sqrt{2}=\dfrac{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}=\dfrac{a}{b}\cdot\dfrac{\sqrt{2}-1}{\sqrt{2}-1}=\dfrac{\sqrt{2}a-a}{\sqrt{2}b-b}=\dfrac{2b-a}{a-b}.\,$ Note $\,2b-a=a\left(\sqrt{2}-1\right)\lt a$. So this fraction has a smaller numerator than the one we had. So this is a contradiction.

Answer 1

Yes, the proof is correct. It is a well-known proof, essentially using denominator descent using the division algorithm, though that is greatly obfuscated. Below I clarify this viewpoint for the generalization below (the OP proof is exactly the special case $\, k = 2\,$ and $\,q = \lfloor \sqrt 2\rfloor = 1)$.

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, so $\,\color{#c00}{\sqrt k = \frac{a}b}$ for naturals $a$ and $b.\,$ Let $\color{#0af}{q =\lfloor \sqrt k\rfloor} $ be the largest integer no greater than $\sqrt k.\,$ Then

$$\begin{aligned} {\sqrt {k}} \,={\frac {a}{b}}&={\frac {a({\sqrt {k}}-q)}{b({\sqrt {k}}-q)}}\\[3pt] &={\frac {\color{#0a0f}a{\sqrt {k}}-aq}{b{\color{#c00}{\sqrt {k}}}-bq}}\\[3pt] &={\frac {\color{#0a0}{b{\sqrt {k}}}{\sqrt {k}}-aq}{\!\!b({\color{#c00}{{a}/{b}}})-bq}}\\[3pt] &={\frac {\color{#0a0}{bk-aq}}{\color{#c00}{a-bq}}}=\,\frac{a'}{b'}\end{aligned}\qquad$$

The numerator and denominator were multiplied by $\sqrt k − q\,$ which is $\rm\color{#0af}{{\rm positive\ and }< 1}$, yielding integers $a'$ and $b'$, which are $\rm\color{#0af}{less}$ than $a$ and $b$ resp. 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} [\![1]\!]\qquad\quad\:\!\ \ b \sqrt k\, &=\, a\qquad\ \, \Rightarrow \text{$\,b\ $ is a denom of }\:\! \sqrt k\\[.2em] \sqrt k\,\cdot\, [\![1]\!]\ \ \, \Rightarrow\,[\![2]\!]\qquad\quad\ \ a\sqrt k\, &=\, bk\qquad \Rightarrow \text{ $a\,$ is a denom of }\:\! \sqrt k\\[.2em] [\![2]\!] - [\![1]\!]\:\!q\,\Rightarrow\,[\![3]\!] \ \ \ \, (\color{#c00}{a\!-\!bq})\sqrt k\, &=\, \color{#0a0}{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.\,$ $\bf\small QED$

---

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

Or we can descend quicker via: $\,a,b$ denoms $\Rightarrow \gcd(a,b)\!=\!1$ is a denom. Or more simply (but slower) via: $\,a>b\,$ denoms $\Rightarrow a-b\,$ denom, as explained here, along with generalizations.

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

Generalization $ $ The same method proves 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 (i.e. $\,\Bbb Z\,$ [or any PID] is integrally-closed), as I explain in a Remark here. There is further discussion of this and related ideas in various posts on denominator ideals.