# 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. – Lord Shark the Unknown Dec 8 '18 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. – Toby Mak Dec 8 '18 at 13:18
• You have a typographical error. ab-a should read $2b-a$. – Ben W Dec 8 '18 at 13:44
• Note that $2b-a<a$ is equivalent to $2b<2a$, which is true because $a>b$. – egreg Dec 8 '18 at 13:57

It is a correct well-known proof. Essentially it uses denominator descent by the division algorithm, though that is obfuscated . Below I clarify this viewpoint for the generalization below. The proof in the question is exactly the special case $$\, k = 2\,$$ and $$\,q = {\rm floor}(\sqrt 2) = 1\,$$ of 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}{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 more conceptually as below, where "$$\,n\,$$ is a denom of $$\,r$$" means that the rational $$\,r\,$$ can be written with denominator $$\,n,\,$$ i.e. $$\,n\,r = j\,$$ for some integer $$\,j.$$

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

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 initially assume that $$\,b\,$$ is the least denominator then deduce a contradiction that a smaller denominator exists if $$\,b\,$$ doesn't divide $$\,a.$$

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.