On √2

Yiannis Petridis connects square roots and continued fractions

post

Image: Hitoaki Koishikawa, CC BY-SA 3.0

One of the first theorems lots of students see is that the square root of two is irrational (ie not a fraction). Therefore, we cannot restrict our attention to rational numbers only. Clearly $\sqrt{2}$ is a number we must have, as by Pythagoras’ theorem it represents the length of the hypotenuse of a right-angled isosceles triangle with vertical sides $1$. What the theorem says is that $\sqrt{2}$ is never $x/y$ with $x$, $y$ integers. Or, to put it another way, $$2\ne \frac{x^2}{y^2}\Leftrightarrow x^2\ne 2y^2,$$ that is, the square of an integer is never twice the square of another integer. However, they are both integers. The closest they can be apart is $1$, ie $$x^2-2y^2=\pm 1.$$ This is the simplest form of Pell’s equation: $x^2-Ny^2=\pm 1$. When $N =2$, one can easily find a solution in the integers $(x, y)=(1, 1)$. With a little more thinking we find the solutions

$(x, y)$ Why?
$(1, 1) $ $1^2-2\cdot 1^2=-1$
$(3, 2) $ $3^2-2\cdot 2^2=+1$
$(7, 5) $ $7^2-2\cdot 5^2=-1$
$(17, 12)$ $17^2-2\cdot 12^2=+1$

The last one is more challenging. Why do we care? Writing $x^2-2y^2=\pm 1$ as $$\left(\frac{x}{y}\right)^2=2\pm\frac{1}{y^2},$$ we see that finding solutions to Pell’s equation with larger denominator produces fractions $x/y$ with squares closer to $2$, ie better approximations of $\sqrt{2}$, since $1/y^2$ will be smaller. For instance the pairs found above produce the approximations $1/1=1$, $3/2=1.5$, $7/5=1.4$, and $17/12=1.4166$ for $\sqrt{2}=1.41421356$. We will see below that we can find infinitely many points with integer coordinates $(x, y)$ satisfying this Pell’s equation. It is desirable to be able to produce them systematically. We start by using the familiar identity $a^2-b^2=(a+b)(a-b)$ to rewrite the first solution $(x,y) = (1,1)$ as $$1^2-2\cdot 1^2=(1+\sqrt{2})(1-\sqrt{2})=-1.$$ This suggests that the number $1+\sqrt{2}$ is important (we call it the fundamental unit). We then observe that \begin{align*} (1+\sqrt{2})^2&=(1+\sqrt{2})(1+\sqrt{2})=3+2\sqrt{2},\\ (1+\sqrt{2})^3&=(3+2\sqrt{2})(1+\sqrt{2})=7+5\sqrt{2},\\ (1+\sqrt{2})^4&=(7+5\sqrt{2})(1+\sqrt{2})=17+12\sqrt{2}. \end{align*} There is a clear pattern that emerges: the coefficients of the expressions on the right are the pairs $(x, y)$ we found above. Let’s write $$(1+\sqrt{2})^n=x_n+y_n\sqrt{2},$$ with $x_n$ and $y_n$ natural numbers (this is guaranteed by the binomial theorem if we expand and collect the terms that contain $\sqrt{2}$ and the terms that do not). Then it seems that $$x_n^2-2y_n^2=\pm 1$$ with $+1$ when $n$ is even and $-1$ with $n$ odd. So to find solutions we have to expand $(1+\sqrt{2})^n$. Using the binomial theorem is not very practical. In fact, we try to find recursive formulae for the two sequences $x_n$ and $y_n$. We have \begin{align*} x_{n+1}+y_{n+1}\sqrt{2}&=(1+\sqrt{2})^{n+1} \\ & =(x_n+y_n\sqrt{2})(1+\sqrt{2}) \\ & =(x_n+2y_n)+(x_n+y_n)\sqrt{2}. \end{align*} We match coefficients to get the recurrences: \begin{equation}\label{recurrence}\tag{*} x_{n+1}=x_n+2y_n, \quad y_{n+1}=x_n+y_n. \end{equation} Matching coefficients can be justified because we can rearrange to get $$\sqrt{2}=\frac{x_{n+1}-x_n-2y_n}{x_n+y_n-y_{n+1}},$$ with integer numerator and denominator. If $y_{n+1}$ is not equal to $x_n+y_n$, we get that $\sqrt{2}$ is rational. We can apply \eqref{recurrence} repeatedly to the pair $(17, 12)$ to get new solutions leading to better approximations of $\sqrt{2}$:

$(x, y)$ $x/y$
$(41, 29)$ $ 1.4137$
$(99, 70)$ $ 1.41428$
$(239, 169)$ $ 1.41420$

Using \eqref{recurrence}, we see that \begin{equation} \label{blah}\tag{**} x_{n+1}^2-2y_{n+1}^2 =(x_n+2y_n)^2-2(x_n+y_n)^2 =-(x_n^2-2y_n^2). \end{equation} If $x_n^2-2y_n^2=+1$, then $x_{n+1}^2-2y_{n+1}^2=-1$ and vice versa. This explains the pattern we found above. In fact, one can actually consider also negative powers of $1+\sqrt{2}$. Since $(1+\sqrt{2})^{-1}=-(1-\sqrt{2})$, we can check that the solutions we get are the same up to the sign of $x_n$ and $y_n$.

An approximate history

John Pell, after whom the equation $x^2 – N y^2 = \pm 1$ is named.

In ancient times, the numerators were called diameter or diagonal numbers and the denominators side numbers, because their ratio tends to the ratio of the hypotenuse divided by the vertical side of any right-angled isosceles triangle. The pair $(7, 5)$ giving the approximation $7/5$ for $\sqrt{2}$ was known to the Pythagoreans and Plato. Pell’s equation $x^2-2y^2=\pm1$ and the recurrence formulae \eqref{recurrence} appear in the work of Theon of Smyrna (On mathematics useful for the understanding of Plato AD 130—about 1500 years before Pell) and must have been known to Plato and likely the Pythagoreans according to Commentary on Plato’s republic by Proclus. For a fuller history, see A history of Greek mathematics, vol. I by Thomas Heath (pages 91–93), and Greek mathematical works I by Ivor Thomas (pages 132–139). In fact, Proclus refers to Euclid (Euclid II.10) for the proposition \begin{equation*}\label{geometric}(x+2y)^2+x^2=2(x+y)^2+2y^2,\end{equation*} which is equivalent to \eqref{blah}, and is exactly what we saw for the solutions $(x_n, y_n)$.

Around AD 250, Diophantus considered integer solutions of the equation $$ a^2 x^2+c=y^2$$ for various $(a, c)$, eg $x^2+1=y^2$, $x^2-1=y^2$, $x^2+12=y^2$. This is closely related to Pell’s equations. The great Indian mathematician Brahmagupta (born AD 598) discovered the identity $$(a^2-Nb^2)(x^2-Ny^2)=(ax+Nby)^2-N(ay+bx)^2,$$ which helps produce new solutions from old. The solution of the general Pell’s equation is due to Bhaskara II (12th century). Pell himself was an English mathematician alive in the 17th century, and is connected to the problem thanks to Euler, who mistakenly believed that a commentary Pell had written on the equation was in fact his own original work.

The geometric approach

There is a geometric interpretation of the construction in \eqref{recurrence}, which associates the solutions we’ve found to points on a curve in the plane. The equations $x^2-2y^2=\pm 1$ represent two hyperbolae in the plane with asymptotes $y=\pm x/\sqrt{2}$. They meet the axes at the points $(\pm 1, 0)$ and $(0, \pm 1/\sqrt{2})$. We search for points on these hyperbolae with coordinates in the natural numbers (we might as well concentrate on the first quadrant $x, y\ge 0$). The closest point to the origin is $(1, 0)$. The next closest is $(1, 1)$. Starting from a point $(x_n, y_n)$ on either hyperbola, we draw the tangent line to the hyperbola at that point. Implicit differentiation gives $2x-4yy’=0\implies y’=x/(2y)$, so that the slope of the tangent line is $x_n/(2y_n)$. At the same time the line from $(x_{n+1}, y_{n+1})$ to $(x_n , y_n)$ has slope $$\frac{y_{n+1}-y_n}{x_{n+1}-x_n}=\frac{x_n}{2y_n},$$ with the help of \eqref{recurrence}. We conclude that this line is the tangent line at $(x_n, y_n)$. To find the next solution, we draw the tangent line at $(x_n, y_n)$ and find its point of intersection with the other hyperbola. So not only does the tangent line intersect the other hyperbola, but it intersects at a point with integer coordinates! This construction is called the tangent construction and predates the famous geometric construction of the group law on elliptic curves. The figure below shows the two hyperbolae and the tangent at $(1,1)$.

We can also understand the sign of the remainder $\pm 1$ using this geometric approach. The slope of the asymptote $y=x/\sqrt{2}$ is $1/\sqrt{2}$. If $(x_n, y_n) $ is on the hyperbola $x^2-2y^2=-1$, then $y_n$ is relatively large compared to the asymptote, so $y_n/x_n>1/\sqrt{2}\iff x_n/y_n<\sqrt{2}.$ The slope of the tangent line is smaller than the one of the asymptote. Similarly, if $(x_n, y_n) $ is on the hyperbola $x^2-2y^2=1$, then $y_n$ is relatively small compared to the asymptote, so $y_n/x_n<1/\sqrt{2}\iff x_n/y_n>\sqrt{2}.$ The slope of the tangent line is larger than the one of the asymptote. In both cases the tangent line at $(x_n, y_n)$ will cross the asymptote and meet the other hyperbola at the point $(x_{n+1}, y_{n+1})$ with larger coordinates. As the tangent lines get squeezed between the hyperbolae, their slopes approach the slope of the asymptote. We see that $$\frac{x_1}{y_1}<\frac{x_3}{y_3}<\frac{x_5}{y_5}<\cdots <\sqrt{2}<\cdots <\frac{x_4}{y_4}<\frac{x_2}{y_2}.$$ This means that we have trapped $\sqrt{2}$ from above and below by the corresponding fractions. Using the fractions $239/169$ and $99/70$ we see that we found the first four decimal digits of $\sqrt{2}\approx 1.4142$.

Other forms of Pell’s equation

If one tries to work with Pell’s equation $x^2-3y^2=\pm 1$ in order to approximate $\sqrt{3}$, then this can only be done with $+1$ (the reader may be interested to investigate why). The fundamental unit here is not $1+\sqrt{3}$ but $2+\sqrt{3}$. This provides the smallest solution of the equation: $(2, 1)$. The recurrence relations are different but equally easy to find: $x_{n+1}=2x_n+3y_n$, $y_{n+1}=x_n+2y_n$, producing from $(2, 1)$ the solutions $(7, 4)$, $(26, 15)$ etc. Since $x_n^2$ is always greater than $3y_n^2$, the method provides approximations of $\sqrt{3}$ that are always larger than $\sqrt{3}$. In both cases of Pell’s equation discussed so far ($\sqrt{2}$ and $\sqrt{3}$) it was easy to spot the smallest solution in the natural numbers. But this becomes increasingly hard: for $x^2-Ny^2=1$ and $N= 13$ the smallest solution is $(649 ,180 )$. Frenicle challenged Wallis to solve the equation with $N=313$. The smallest solution is $(32188120829134849, 1819380158564160)$. The Archimedes cattle problem (see Greek mathematical works II, Ivor Thomas, page 202), which Gotthold Ephraim Lessing discovered as a poem of forty-four lines in a Greek manuscript, leads to Pell’s equation $ x^{2}-410286423278424y^{2}=1$. Here the smallest solution has 206,545 digits if written out explicitly.

How does one proceed to find the smallest solution to Pell’s equation without guessing? There is a systematic technique using continued fractions. Let’s start with $\sqrt{2}$. We write $$\sqrt{2}=(\sqrt{2} + 1) – 1 = 1+\frac{1}{\sqrt{2}+1}=1+\frac{1}{2+\frac{1}{\sqrt{2}+1}}$$ $$=1+\frac{1}{2+\frac{1}{2+\frac{1}{\sqrt{2}+1}}}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{\sqrt{2}+1}}}}=\cdots$$ using always that $\sqrt{2}+1=2+\frac{1}{\sqrt{2}+1}$. Ignoring the last fraction with the square root, we are led to consider the fractions $$1+\frac{1}{2}=\frac{3}{2},\quad 1+\frac{1}{2+1/2}=1+\frac{1}{5/2}=\frac{7}{5},\quad 1+\frac{1}{2+\frac{1}{2+\frac{1}{2}}}=\frac{17}{12}, \quad \cdots$$ The fractions we get are called the convergents $p_n/q_n$ for the continued fraction of $\sqrt{2}$, which we write $[1;\overline 2]$, with the bar denoting that the pattern $2$ repeats itself at infinity. The convergents $p_n/q_n$ are the same rational approximations that we found above. This can be seen by writing recurrence relations for $p_n$ and $q_n$: $$p_{n+1}=p_n+2q_n, \quad q_{n+1}=p_n+q_n,$$ which are the same as \eqref{recurrence}. It is true that the smallest solution of Pell’s equation $(x, y)$ will be among the pairs $(p_n, q_n)$, and, therefore, may be found by performing the continued fraction expansion and testing each successive convergent. From the calculation $$\sqrt{3}=1+(\sqrt{3}-1)=1+\frac{2}{\sqrt{3}+1}=1+\frac{1}{1+(\sqrt{3}-1)/2}=1+\frac{1}{1+\frac{1}{2+(\sqrt{3}-1)}}=\cdots$$ it is not too hard to see that $\sqrt{3}=[1; \overline{1,2}]$. For $N=313$ it is a lot more difficult: $\sqrt{313}= [17; \overline{1, 2, 4, 11, 1, 1, 3, 2, 2, 3, 1, 1, 11, 4, 2, 1, 34}]$. The origins of continued fractions go back to Euclid and the Euclidean algorithm to find the greatest common divisor of two numbers. Rafael Bombelli in L’Algebra (1572) essentially proved that $\sqrt{13} $ has the infinite continued fraction $$\sqrt{13}= 3+\frac{4}{6+\frac{4}{6+\frac{4}{6+\cdots}}},$$ this being the first time that square roots and continued fractions are related. Even now there are open questions on the continued fraction expansion of numbers like $\sqrt[3]{2}$.

Yiannis is a professor of mathematics at University College London. He works in analytic number theory, can write with both hands, and really likes polar bears.
+ More articles by Yiannis

More from Chalkdust