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 > 3\), then

\[ \left| \frac{p}{q} - \sqrt{D} \right| = \frac{1}{(p + q\sqrt{D})q} < \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' > x\) if and only if \(y' > 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 < r + s\sqrt{D} < (p+q\sqrt{D})^{m+1} \]

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

\[ 1 < t + u \sqrt{D} < 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 > 0\) then we have a smaller positive solution, contradicting the minimality of \(p,q\).

We have \(t > 0\) because \(r > s\sqrt{D}\) and \(p_m > 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 > 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 💡

The Pell Equation

Contents