Exercise 6.3.5 (Theaethetus)

Proof.

(i)

Suppose that $\sqrt{77}$ is rational, and define $$A=\left\{q\in {\mathbb{N}}^{\text{∗}}\mid \exists <!--\; FUNCTION\; APPLICATION\; -->p\in \mathbb{Z},\sqrt{77}=\frac{p}{q}\right\}.$$

By our hypothesis, $A\ne \varnothing$, thus $b=\min <!--\; FUNCTION\; APPLICATION\; -->(A)$ exists, and $\sqrt{77}=a∕b$ for some integer $a$. Then $a^2=77b^2$, and $a\ne 8b$ (otherwise $\sqrt{77}=8$, so $77=64$, which is false). Moreover

$$\begin{array}{llll}\hfill \frac{a}{b}=\frac{77b-8a}{a-8b}& ⟺a^2-8\mathit{ab}=77b^2-8\mathit{ab}& \hfill & \\ \hfill & ⟺a^2=77b^2.& \hfill & \end{array}$$

This shows that

$$\begin{array}{llll}\hfill \sqrt{77}=\frac{a}{b}& =\frac{77b-8a}{a-8b}.& \hfill & \end{array}$$

Since $8^2<77<9^2$, we obtain $8<a∕b<9$, thus $8b<a<9b$, which gives

$$0<a-8b<b.$$

Since $a-8b>0$ and $\sqrt{77}=(77b-8a)∕(a-8b)$, then $a-8b\in A$. But $b=\min <!--\; FUNCTION\; APPLICATION\; -->(A)$, so $b\le a-8b$, in contradiction with $a-8b<b$. This shows that $\sqrt{77}$ is irrational.

(ii)

Let $n$ be a positive integer not a perfect square., and suppose that $\sqrt{n}$ is rational. Then $$A=\left\{q\in {\mathbb{N}}^{\text{∗}}\mid \exists <!--\; FUNCTION\; APPLICATION\; -->p\in \mathbb{Z},\sqrt{n}=\frac{p}{q}\right\}\ne \varnothing ,$$

so $b=\min <!--\; FUNCTION\; APPLICATION\; -->(A)$ exists, and $\sqrt{n}=a∕b$ for some integer $a$, so $a^2=n{b}^2$.

Put $k=\lfloor \sqrt{n}\rfloor$. Then $k\le \sqrt{n}<k+1$. Moreover $k\ne \sqrt{n}$, otherwise $n=k^2$ is a perfect square. Therefore $k<\sqrt{n}<k+1$, and $\mathit{kb}<a<(k+1)b$, so

$$\begin{array}{lll}\hfill 0<a-\mathit{kb}<b.& & \hfill \text{(1)}\end{array}$$

Since $a-\mathit{kb}\ne 0$,

$$\begin{array}{llll}\hfill \frac{a}{b}=\frac{\mathit{nb}-\mathit{ka}}{a-\mathit{kb}}& ⟺a^2-\mathit{kab}=n{b}^2-\mathit{kab}& \hfill & \\ \hfill & ⟺a^2=n{b}^2.& \hfill & \end{array}$$

This shows that

$$\begin{array}{llll}\hfill \sqrt{n}=\frac{a}{b}& =\frac{\mathit{nb}-\mathit{ka}}{a-\mathit{kb}}.& \hfill & \end{array}$$

Since $a-\mathit{kb}>0$ and $\sqrt{n}=\frac{\mathit{nb}-\mathit{ka}}{a-\mathit{kb}}$, we obtain $a-\mathit{kb}$ in $A$. But $b=\min <!--\; FUNCTION\; APPLICATION\; -->(A)$, so $b\le a-\mathit{kb}$, in contradiction with $a-\mathit{kb}<b$. This shows that $\sqrt{n}$ is irrational.