Exercise 4.4.3 (Irrationality of $\sqrt{2}$)

Proof. Suppose for sake of contradiction that we had a rational number $x$ for which $x^2=2$. Clearly $x$ is not zero. We may assume that $x$ is positive, for if $x$ were negative then we could just replace $x$ by $-x$ (since $x^2={(-x)}^2$). Thus $x=p∕q$ for some positive integers $p,q$, so ${(p∕q)}^2=2$, which we can rearrange as $p^2=2q^2$. Define a natural number $p$ to be even if $p=2k$ for some natural number $k$, and odd if $p=2k+1$ for some natural number $k$. Every natural number is either even or odd, but not both.

(why? : by Proposition 2.3.9, the Euclidean division of $p$ by $2$ gives a quotient $k$ and a remainder $r$ such that $p=2k+r,0\le r<2$, so $r=0$ or $r=1$. This shows that every natural number is even or odd. If $p$ is simultaneously even and odd, then $p=2k=2l+1$ for some natural numbers $k,l$. Then $2(k-l)=1$, where $k-l>0$, thus $k-l\in \mathbb{N}\setminus \{0\}$ , so $1=2(k-l)\ge 2$, this is a contradiction since $1<2$ (I avoid here to use $2\mid 1$ !). This shows that $p$ is either even or odd, but not both.)

If $p$ is odd, then $p^2$ is also odd,

(why? : if $p$ is odd, $p=2k+1$ for some $k\in \mathbb{N}$, then $p^2={(2k+1)}^2=4k^2+4k+1=2(2k^2+2k)+1=2l+1$, where $l=2k^2+2k\in \mathbb{N}$, so $p^2$ is odd.)

which contradicts $p^2=2q^2$. Thus $p$ is even, i.e., $p=2k$ for some natural number $k$. Since $p$ is positive, $k$ must also be positive. Inserting $p=2k$ into $p^2=2q^2$, we obtain $4k^2=2q^2$, so that $q^2=2k^2$.

To summarize, we started with a pair $(p,q)$ of positive integers such that $p^2=2q^2$, and ended with a pair $(q,k)$ of positive integers such that $q^2=2k^2$. Since $p^2=2q^2$, we have $q<p$.

(why? : Since $q>0$, $q^2<q^2+q^2=2q^2=p^2$, thus $q<p$. Indeed, if $q\ge p\ge 0$, $q^2\ge p^2$.)

If we rewrite $p^{\prime }:=q$, and $q^{\prime }:=k$, we thus can pass from one solution $(p,q)$ to the equation $p^2=2q^2$ to a new solution $(p^{\prime },q^{\prime })$ to the same equation which has a smaller value of $p$. But then we can repeat this procedure again and again obtaining a sequence $(p^{″},q^{″}),(p^{‴},q^{‴})$, etc. of solutions to $p^2=2q^2$, each one with a smaller value of $p$ than the previous, and each one consisting of positive integers. But this contradicts the principle of infinite descent (see Exercise 4.4.2). This contradiction shows that we could not have had a rational $x$ for which $x^2=2$. □