$\sqrt{2}$ proved irrational by denominator descent on $\sqrt 2 - 1$

Question

I found the following proof arguing for the irrationality of $\sqrt{2}$.

Suppose for the sake of contradiction that $\sqrt{2}$ is rational, and choose the least integer $q > 0$ such that $(\sqrt{2} - 1)q$ is a nonnegative integer. Let $q'::= (\sqrt{2} - 1)q$. Clearly $0 < q' < q$. But an easy computation shows that $(\sqrt{2} - 1)q'$ is a nonnegative integer, contradicting the minimality of $q$.

Clearly, this is a vague proof in that it expects the reader to work out the math involved on his own. I took that as an exercise and worked out the following:

Assuming $\sqrt{2}$ to be rational, let $$\sqrt{2} = \frac{p}{q}$$ where $p$ and $q$ are least possible integers.

Clearly then, $\sqrt{2} - 1$ would also be rational, $$\sqrt{2} - 1 = \frac{p-q}{q}$$ where both $(p-q)$ and $q$ are also integers.

Multiplying both sides by $q$, we get $$(\sqrt{2} - 1)q = (p-q) = q'$$ where $q'$ is an integer. Using, $2>\sqrt{2} > 1$ , we get $$1>\sqrt{2}-1>0$$ proving that $q'$ is a non-negative integer.

As stated in the proof, computing $(\sqrt{2}-1)q'$ we get, $$(\sqrt{2}-1)q' = \frac{(p-q)^2}{q}$$which is not necessarily an integer (in fact necessarily not an integer). However, the proof claims it to be.

Am I missing something or something is wrong with how I proceeded?

Here is a link to the textbook where I found this proof: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/readings/MIT6_042JS15_textbook.pdf, (p 32, problem 1.14).

P.S. This is my first post here and my first time with TeX. I'd also like to know if there is anything wrong with the way my question is presented.

Answer 1

$$(\sqrt2-1)q'=(\sqrt2-1)(\sqrt2-1)q=(3-2\sqrt2)q=q+2(1-\sqrt 2)q =q-2q'$$

Answer 2

This well-known proof is usually presented as rote algebra - without any explanation of the (beautiful!) innate arithmetical structure that underlies the proof. Below we bring this to the fore, which simplifies the algebra and yields conceptual insight. First we consider a simpler variant.

Suppose that $w := \sqrt 2 = p/q$ for integers $p,q>0.\,$ Then $ w^2 = 2\,\Rightarrow\, w = 2/w = 2q/\color{#c00}p.\,$ Therefore if $w =\sqrt 2 $ is a fraction $p/q$ then its numerator $\color{#c00}p$ can also serve as a denominator for $w$. This peculiar property easily leads to contradictions, e.g. if we choose $q$ as the least denominator (so $p/q\,$ is in lowest terms) then (as well-known) every denominator must be a multiple of $q.\,$ In particular $\color{#c00}p$ must a multiple of $q,\,$ thus $\,w = p/q\,$ is an integer, contra $w^2 = 2.$

Your proof is a slight variant of this. Instead of using said divisibility property of least denominators (reduced fractions) it essentially employs the core of a descent-based proof of this property. Namely, call $n$ a denominator of a fraction $w$ if $nw \in \Bbb Z,\,$ i.e. if $\,w = k/n\,$ for some integer $k$. The set of all denominators of a fraction enjoys a special structure - it is closed under subtraction since $\,nw,mw\in\Bbb Z\,\Rightarrow\, (n\!-\!m)w = nw-mw\in\Bbb Z.\,$ A simple descent proof using division with remainder shows that such sets of integers are precisely the set of multiples of their least positive element. In particular, the least denominator of $w$ divides every denominator of $w$.

The descent step in this proof works as follows: If $p > q$ are denominators then, by closure under subtraction, so too are $\,p\!-\!q,\, p\!-\!2q,\,\ldots$ hence so too is the least positive integer in this sequence $= p\bmod q$, i.e. denominators are closed under mod = remainder. So if $q$ is the least denominator then it must divide $p$ else $0\neq p\bmod q$ would be a smaller denominator.

The proof you found is a slight variant. By instead starting with a fraction $\ w = \sqrt{2}-1 = p/q$ which is less than $1$ we force $p< q\,$ so there is no need to mod $p$ by $q$ to get a smaller denominator (effectively the mod has already been done by subtracting from $\sqrt 2$ its integer part $=1),\,$ as in Theorem 2). Thus that $\,q':=p = q(\sqrt 2-1)$ serves as a smaller denominator is a special case of the above general method of denominator descent. While one can verify $q'=p< q$ by rote algebra, doing so in absence of the innate algebraic structure greatly obfuscates comprehension of the essence of the matter. See this answer for explicit details.

Remark $ $ This innate algebraic structure will be clarified when one studies ideals in abstract algebra and number theory. The fact that denominators are closed under subtraction means that they form an ideal of the ring $\Bbb Z $ of integers, and the denominator divisibility property is a special case of the fact that such ideals are principal (singly generated), i.e. have form $ n\Bbb Z.\,$ Finally the fact that the numerator also serves as a denominator generalizes to Dedekind's notion of conductor ideal - which yields an abstract way of encapsulating the descent in such elementary proofs of irrationality. See also my posts on denominator ideals and, more generally, order ideals.