# The Pell Equation

The equation

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

**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

**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

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

Rearranging, and equating rational and irrational parts yields

Eliminating \(a_1\):

**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

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

which rearranges to

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

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

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

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

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

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

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

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

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

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. ∎

*blynn@cs.stanford.edu*💡