Pell's Equation

The so-called ``Pell's equation'' is $x^2-dy^2=1$ with $d>0$ square free, and we seek integer solutions $x,y$ to this equation. If $x+y\sqrt{d}\in K = \mathbf{Q}(\sqrt{d})$, then

$$\Norm (x+y\sqrt{d}) = (x+y\sqrt{d})(x-y\sqrt{d}) = x^2 -dy^2.$$

Thus if $(x,y)$ are integers such that $x^2-dy^2=1$, then $\alpha = x + \sqrt{d}y \in \O_K$ has norm $1$, so by Proposition 8.1.4 we have $\alpha \in U_K$. The integer solutions to Pell's equation thus form a finite-index subgroup of the group of units in the ring of integers of $\mathbf{Q}(\sqrt{d})$. Dirichlet's unit theorem implies that for any $d$ the solutions to Pell's equation with $x,y$ not both negative forms an infinite cyclic group, which is a fact that takes substantial work to prove using only elementary number theory (for example, using continued fractions).

We first solve Pell's equation $x^2 - 5y^2 = 1$ with $d=5$ by finding the units of the ring of integers of $\mathbf{Q}(\sqrt{5})$ using Sage.

The subgroup of cubes gives us the units with integer $x,y$ (not both negative).

A great article about Pell's equation is [Len02]. The MathSciNet review begins: ``This wonderful article begins with history and some elementary facts and proceeds to greater and greater depth about the existence of solutions to Pell equations and then later the algorithmic issues of finding those solutions. The cattle problem is discussed, as are modern smooth number methods for solving Pell equations and the algorithmic issues of representing very large solutions in a reasonable way.''

The simplest solutions to Pell's equation can be huge, even when $d$ is quite small. Read Lenstra's paper for some examples from over two thousand years ago. Here is one example for $d=10000019$.

Exercise 8.2.1   Let $U$ be the group of units $x+y\sqrt{5}$ of the ring of integers of $K=\mathbf{Q}(\sqrt{5})$.

1. Prove that the set $S$ of units $x+y\sqrt{5} \in U$ with $x,y\in\mathbf{Z}$ is a subgroup of $U$. (The main point is to show that the inverse of a unit with $x,y\in\mathbf{Z}$ again has coefficients in $\mathbf {Z}$.)
2. Let $U^3$ denote the subgroup of cubes of elements of $U$. Prove that $S=U^3$ by showing that $U^3\subset S \subsetneq U$ and that there are no groups $H$ with $U^3\subsetneq H \subsetneq U$.