# The Pell Equation

The equation

$x^2 - D y^2 = 1$

over the integers for some nonsquare positive $$D$$ is known as the Pell equation. We consider a slighty more general variant of the equation:

$x^2 - D y^2 = \pm 1$

Theorem: If $$D$$ is a nonsquare positive integer whose continued fraction expansion has a repeating portion of $$k$$ terms, then $$p_k , q_k$$ is a solution of

$x^2 - D y^2 = (-1)^k$

Proof: Let $$\sqrt{D} = [a_1; a_2, ...]$$ and $$x_i = [a_i; a_{i+1}, ...]$$. We have $$x_2 = x_{k+2}$$ which means

$\sqrt{D} = \frac{x_{k+2}p_{k+1} + p_k}{x_{k+2}q_{k+1} + q_k} = \frac{x_2 p_{k+1} + p_k}{x_2 q_{k+1} + q_k}$

and $$x_2 = 1 / (\sqrt{D} - a_1)$$, whence

$\sqrt{D} = \frac{p_{k+1} + p_k(\sqrt{D}-a_1)}{q_{k+1} + q_k(\sqrt{D}-a_1)}$

Rearranging, and equating rational and irrational parts yields

\begin{aligned} q_{k+1} - a_1 q_k - p_k &=& 0 \\ p_{k+1} - a_1 p_k - q_k D &=& 0 \end{aligned}

Eliminating $$a_1$$:

$-p_k q_{k+1} + q_k p_{k+1} + p_k^2 - D q_k^2 = 0 ∎$

Theorem: If $$p,q$$ is a solution of $$x^2 - D y^2 = \pm 1$$ and $$p, q$$ are coprime then $$p/q$$ is a convergent of $$\sqrt{D}$$.

Proof: If $$D \gt 3$$, then

$\left| \frac{p}{q} - \sqrt{D} \right| = \frac{1}{(p + q\sqrt{D})q} \lt \frac{1}{2 q^2}$

and the result follows from a theorem on the accuracy of convergents. We can explicitly verify the cases $$D = 2, 3$$.∎

Theorem: If the $$r$$th convergent of $$\sqrt{D}$$ gives a solution of $$x^2 - D y^2 = \pm 1$$ then $$k | r$$ where $$k$$ is the number of terms in the period of the expansion.

Proof: Define $$x_k = [a_k; a_{k+1}, ...]$$. It is enough to show $$x_{r+2} = x_2$$ when the $$r$$th convergent gives a solution of the Pell equation: if $$P, Q$$ are the smallest positive integers such that $$P^2 - D Q^2 = \pm 1$$, then from the previous theorem, $$P/Q$$ is the $$R$$th convergent for some $$R$$, and we would have $$x_{R+2} = x_2$$, and also $$k = R$$ (otherwise we would have a smaller solution than $$P, Q$$ since $$x_{k+2} = x_2$$).

We replace $$\pm 1$$ with $$(-1)^r$$ in the equation since odd convergents are less than $$\sqrt{D}$$ while even convergents are greater.

We have

$\sqrt{D} = \frac{p_r x_{r+1} + p_{r-1}}{q_r x_{r+1} + q_{r-1}}$

which rearranges to

$(p_r - \sqrt{D} q_r)x_{r+1} = -p_{r-1} + \sqrt{D} q_{r-1}$

Applying $$p_r^2 - D q_r^2 = (-1)^r$$ gives

$x_{r+1} = \sqrt{D} + (-1)^r (D q_r q_{r-1} - p_r p_{r-1})$

That is, $$x_{r+1}$$ is $$\sqrt{D}$$ plus some integer. From our work on periodic continued fractions, we must have $$x_2 = x_{r+2} ∎$$

Theorem: The expansion of $$\sqrt{D}$$ for a nonsquare positive integer $$D$$ has the form

$[a_1; a_2, a_3, a_4, ..., a_4, a_3, a_2, 2a_1,...]$

with $$a_2,a_3,..., 2 a_1$$ repeating.

Proof: Considering the relationship between Euclid’s algorithm and the computation of convergents, or directly from the recurrence relation, we have

$\frac{q_{k+1}}{q_k} = [a_{k+1}; a_k, ..., a_2 ]$

In the proof of our first theorem on Pell equations, we found

$q_{k+1} - a_1 q_k - p_k = 0$

if $$p_k, q_k$$ is a solution. Since $$a_1 + \frac{p_k}{q_k} = [2a_1;a_2, ..., a_k]$$, we have

$[a_{k+1}; a_k, ..., a_2] = [2a_1;a_2 , ..., a_k] ∎$

If $$x', y'$$ and $$x, y$$ are solutions to $$x^2 - D y^2 = \pm 1$$, observe $$x' \gt x$$ if and only if $$y' \gt y$$. We use this in the following proof.

Theorem: If $$p,q$$ is the smallest positive solution of the equation $$x^2 - D y^2 = \pm 1$$, then all positive solutions $$p_n, q_n$$ are given by

$(p+q\sqrt{D})^n = p_n + \sqrt{D} q_n$

where $$n$$ is odd for when the minus sign is chosen, and any integer when the plus sign is chosen.

Proof: Since $$(p - q\sqrt{D})^n = p_n - \sqrt{D} q_n$$, we find $$(p^2 - D q^2 )^n = p_n^2 - D q^2$$, thus $$p_n, q_n$$ indeed satisfies the equation if $$p, q$$ does.

First suppose the plus sign is chosen, and we have a standard Pell equation. Suppose $$r, s$$ is a solution such that

$(p+q\sqrt{D})^m \lt r + s\sqrt{D} \lt (p+q\sqrt{D})^{m+1}$

for some $$m$$. Divide through by $$p_m + q_m \sqrt{D}$$ to obtain

$1 \lt t + u \sqrt{D} \lt p + q\sqrt{D}$

where $$t + u\sqrt{D} = (r+s\sqrt{D})(p_m - q_m\sqrt{D})$$.

Replacing $$\sqrt{D}$$ with $$-\sqrt{D}$$ and multiplying shows that $$t, u$$ is a (not necessarily positive) solution of the Pell equation. If $$t, u \gt 0$$ then we have a smaller positive solution, contradicting the minimality of $$p,q$$.

We have $$t \gt 0$$ because $$r \gt s\sqrt{D}$$ and $$p_m \gt q_m\sqrt{D}$$, as they are solutions of the Pell equation. We observe $$u$$ has the same sign as

$(p_m s - q_m r)(p_m s + q_m r) = p_m^2 s^2 - q_m^2 r^2 = s^2(D q_m^2 + 1) - q_m^2 (D s^2 + 1) = s^2 - q_m^2$

Since $$s \gt q_m$$ we are done.

For the minus sign variant of the equation, we argue similarly, with $$m$$ and $$m + 2$$ where $$m$$ is odd. ∎

Ben Lynn blynn@cs.stanford.edu 💡