Pell Equations

Suppose we wish to solve

\[ x^2 - D y^2 = 1 \]

where $D$ is not a square. First we compute the continued fraction expansion of $\sqrt{D}$.

\[ \array { P_0 &=& 0 \\ Q_0 &=& 1 \\ a_0 &=& {\lfloor\sqrt{D}\rfloor} \\ P_1 &=& a_0 \\ Q_1 &=& D - a_0^2 \\ a_n &=& {\lfloor \frac{a_0 + P_n}{Q_{n}} \rfloor} \\ P_n &=& a_{n-1} Q_{n-1} - P_{n-1} \\ Q_n &=& \frac{D - P_n^2}{Q_{n-1}} } \]

Then the continued fraction expansion of $\sqrt{D}$ is

\[ \sqrt{D} = [a_0; a_1, ..., a_{k+1}, a_1, ..., a_{k+1}, ... ] \]

It turns out $a_{k+1} = 2 a_0$.

The convergents are computed by

\[ \array { p_0 &=& a_0 \\ p_1 &=& a_0 a_1 + 1 \\ p_n &=& a_n p_{n-1} + p_{n-2} \\ q_0 &=& 1 \\ q_1 &=& a_1 \\ q_n &=& a_n q_{n-1} + q_{n-2} \\ } \]

The convergents satisfy

\[ p_n^2 - D q_n^2 = (-1)^{n+1}Q_{n+1} \]

and $(x, y) = (p_k, q_k)$ is the smallest integer solution of the Pell equation for odd $k$, and $(x, y) = (p_{2k + 1}, q_{2k+1})$ if $k$ is even. From a minimal positive solution $(t,u)$, we may generate the other positive solutions $(x,y)$ via

\[ x+y\sqrt{D} = (t + u\sqrt{D})^n \]

for all positive $n$.

Generalized Pell Equations

Now consider the equation

\[ x^2 - D y^2 = N \]

If $N^2 \lt D$ we may do the following. Compute the convergents $p_n, q_n$ until the smallest integer solution of the Pell equation $x^2 - D y^2 = 1$ is found. In the meantime, check if each $p_n, q_n$ satisfies $p_n^2 - D q_n^2 = N / f^2$ for some $f \gt 0$. If so, append $(f p_n , f q_n)$ to the list of solutions.

We now use this list of solutions to generate all other solutions. If $(r,s)$ is on the list, and $(t,u)$ is a minimal positive solution of the corresponding Pell equation, then we have a family of solutions $(x,y)$ given by

\[ x + y \sqrt{D} = (r + s \sqrt{D})(t + u \sqrt{D})^n \]

for all positive $n$.

If $N^2 \ge D$ then one possibility is brute force. If $N \gt 0$ set $L_1 = 0, L_2 = \sqrt{N(t-1)/{2 D})}$, otherwise set $L_1 = \sqrt{-N/D}, L_2 = \sqrt{-N(t+1)/(2D)}$. For $L_1 \le y \le L_2$ check if $N + D y^2 = x^2 $ for some integer $x$. If so, then append $(x,y)$ to the list of fundamental solutions. Also append $(-x,y)$ if not equivalent to $(x,y)$. (TODO: can avoid since we don’t want negative solutions?) Then proceed as above to generate all solutions.