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