mathschallenge.net

Problem

Consider the Pell equation, $x^2 - 2y^2 = 1$, where $x$ and $y$ are positive integers.

The smallest solution is (3,2), with subsequent solutions being (17,12), (99,70), (577,408), ...

What is most interesting is that the sequence of solutions produce convergents for $\sqrt{2} = 1.414213...$

$\begin{align}\dfrac{3}{2} &= 1.5\\\dfrac{17}{12} &= 1.416666...\\\dfrac{99}{70} &= 1.414285...\\\dfrac{577}{408} &= 1.414215....\end{align}$

Assuming that at least one solution exists, prove that the ordered solutions of the equation $x^2 - dy^2 = 1$ produce convergents for $\sqrt{d}$.

---

Solution

From $x^2 - dy^2 = 1$ complete the square to get $(x - \sqrt{d} y)(x + \sqrt{d} y) = 1$, and as both side must be positive we deduce that $x \gt \sqrt{d} y$.

This leads to $x - \sqrt{d} y = \dfrac{1}{x + \sqrt{d} y}$.

Therefore $\dfrac{x}{y} - \sqrt{d} = \dfrac{1}{y(x + \sqrt{d} y)}$; note also that $\dfrac{x}{y} - \sqrt{d}$ will always be positive.

But as $x \gt \sqrt{d} y$ it follows that $\dfrac{x}{y} - \sqrt{d} \lt \dfrac{1}{y(\sqrt{d} y + \sqrt{d} y)} \lt \dfrac{\sqrt{d}}{y(\sqrt{d} y + \sqrt{d} y)}$.

However, $\dfrac{\sqrt{d}}{y(\sqrt{d} y + \sqrt{d} y)} = \dfrac{\sqrt{d}}{\sqrt{d} y(y + y)} = \dfrac{1}{y \times 2y} = \dfrac{1}{2y^2}$.

Hence $0 \lt \dfrac{x}{y} - \sqrt{d} \lt \dfrac{1}{2y^2}$, or $\sqrt{d} \lt \dfrac{x}{y} \lt \sqrt{d} + \dfrac{1}{2y^2}$.

It can be clearly seen that $\dfrac{x}{y}$ will always be greater than $\sqrt{d}$, but as $y$ increases the error, $\dfrac{1}{2y^2}$, decreases.

To complete the proof we must show that infinitely many increasing solutions in $x$ and $y$ can be found in order to approach the limit.

Consider the mapping $(x,y) \rightarrow (x^2 + dy^2,2xy)$:

$$\begin{align}(x^2 + dy^2)^2 - d(2xy)^2 &= x^4 + 2dx^2 y^2 + d^2 y^4 - 4dx^2 y^2\\&= x^4 - 2dx^2 y^2 + d^2 y^4\\&= (x^2 - dy^2)^2\\&= 1\end{align}$$

That is, if $(x,y)$ is a solution to $x^2 - dy^2 = 1$ then $(x^2 + dy^2,2xy)$ is also a solution, and as $2xy \gt y$ we prove that infinitely many solution exist which converge to the limit $\sqrt{d}$.