Different proof that $\sqrt{2}$ is irrational

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.

• Welcome to Mathematics Stack Exchange! For a first post, this is a certainly a well-written one, so +1 from me. – Glorfindel Jun 10 '17 at 8:57
• @Glorfindel Hey! Thanks! – Eulerian Jun 10 '17 at 9:45
• As you want to know what went wrong with your attempt, I point out here. There is nothing wrong with your work. It just happens that your method could not prove the claim. Do not worry if this happens, because it happens to all of us. Otherwise, there should be no unproven statements now. – edm Jun 10 '17 at 10:11
• the proof claims "$(\sqrt{2}-1)q'$ is a nonnegative integer", but you claim "$(\sqrt{2}-1)q'$, which is not necessarily an integer (in fact necessarily not an integer)"... focus on the last point "contradicting the minimality of q"... show that it is an integer – farruhota Jun 10 '17 at 10:15
• The given proof can be restated in a compact form: since the ordinary continued fraction of $\sqrt{2}$ is $[1;2,2,2,2,2,\ldots]$ due to the identity $\alpha=2+\frac{1}{\alpha}$ fulfilled by $\alpha=\sqrt{2}+1$, $\sqrt{2}$ cannot be a rational number. Otherwise, it would have a finite ordinary continued fraction. – Jack D'Aurizio Jun 10 '17 at 17:24

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

• Now we need another proof for that $q-2q'\gt 0$, but I guess it will be simple because we just need to show $\frac{q'}{q}=\sqrt2-1\lt \frac{1}{2}$. – edm Jun 10 '17 at 9:38
• This seems legitimate except the non-negative part needs to be proved as pointed by @edm. Also, could you help me figure out what went wrong with my working? – Eulerian Jun 10 '17 at 9:48

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).$ 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.

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.