Pell's Equation

In the last lesson, the convergent $\frac{8}{3}$ of $\sqrt{7}$ satisfied $8^{2} - 7 \cdot 3^{2} = 1$. That was no accident. The equation $x^{2} - dy^{2} = 1$, named (by a historical mix-up) after John Pell, is solved completely by the continued fraction of $\sqrt{d}$.

Pell's equation. Let $d > 0$ be an integer that is not a perfect square. We want integers with $x^{2} - dy^{2} = 1$. The trivial solution is $(1, 0)$. The fundamental solution $(x_1, y_1)$ is the solution in positive integers with the smallest $y$.

Theorem. The fundamental solution always exists, and $\frac{x_1}{y_1}$ is a convergent of $\sqrt{d}$. Every solution in positive integers comes from its powers: $$x_k + y_k\sqrt{d} = \left(x_1 + y_1\sqrt{d}\right)^{k}, \qquad k = 1, 2, 3, \dots$$

Why it works

Why convergents. Factor: $(x - y\sqrt{d})(x + y\sqrt{d}) = 1$, so $\dfrac{x}{y} - \sqrt{d} = \dfrac{1}{y(x + y\sqrt{d})} < \dfrac{1}{2y^{2}}$. A fraction that close to $\sqrt{d}$ must be one of its convergents (a theorem of Legendre). Why powers. The "norm" $N(x + y\sqrt{d}) = x^{2} - dy^{2}$ is multiplicative: $N(\alpha\beta) = N(\alpha)N(\beta)$, since $(x - y\sqrt{d})$ behaves like a conjugate. So a power of a number of norm 1 has norm 1 again, and a descent argument shows nothing else occurs.

The hyperbola $x^{2} - 2y^{2} = 1$ and its whole-number points $(3, 2)$, $(17, 12)$, $(99, 70)$, $(577, 408)$. Press Next point: each is the last one times $3 + 2\sqrt{2}$, and the view zooms out because they grow so fast.

Worked example: A small search

Find the fundamental solution of $x^{2} - 2y^{2} = 1$.

Try $y = 1$: $1 + 2 = 3$, not a square. $y = 2$: $1 + 8 = 9 = 3^{2}$.
So $(x_1, y_1) = (3, 2)$. It is the convergent $\frac{3}{2}$ of $\sqrt{2} = [1; 2, 2, \dots]$.

Answer: $(3, 2)$.

Worked example: The next solution

Use $(3, 2)$ to find the next solution of $x^{2} - 2y^{2} = 1$.

$(3 + 2\sqrt{2})^{2} = 9 + 12\sqrt{2} + 8 = 17 + 12\sqrt{2}$.
So $(x_2, y_2) = (17, 12)$. Check: $289 - 2 \cdot 144 = 1$.

Answer: $(17, 12)$.

Worked example: With the continued fraction

Find the fundamental solution of $x^{2} - 7y^{2} = 1$.

$\sqrt{7} = [2; \overline{1, 1, 1, 4}]$ has convergents $\frac{2}{1}, \frac{3}{1}, \frac{5}{2}, \frac{8}{3}, \dots$
$p^{2} - 7q^{2}$ for these: $4 - 7 = -3$, $9 - 7 = 2$, $25 - 28 = -3$, $64 - 63 = 1$.
The first $+1$ is at $\frac{8}{3}$.

Answer: $(8, 3)$.

Solutions can be startlingly large. For $d = 13$ the fundamental solution is $(649, 180)$; for $d = 61$ it is $x = 1{,}766{,}319{,}049$, $y = 226{,}153{,}980$, a challenge Fermat set for other mathematicians in 1657. A search over $y$ would take ages; the continued fraction finds it in a few dozen steps.

Common mistake

Offering $x = 1$, $y = 0$ as the fundamental solution. It solves the equation, but it is the trivial one, and its powers are all $(1, 0)$ again. The fundamental solution is the smallest with $y > 0$; for $d = 2$ that is $(3, 2)$.

Key idea

$x^{2} - dy^{2} = 1$: the fundamental solution is the first convergent $\frac{p}{q}$ of $\sqrt{d}$ with $p^{2} - dq^{2} = 1$, and all positive solutions are the powers $(x_1 + y_1\sqrt{d})^{k}$.

Pell's Equation

Practice

Builds on

Leads to

Sources and further reading