## Pell Equations

For details see my notes on Pell equations.

Suppose we wish to solve

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

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

It turns out \(a_{k+1} = 2 a_0\).

The convergents are computed by

The convergents satisfy

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

for all positive \(n\).

## Generalized Pell Equations

Now consider the equation

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

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.

*blynn@cs.stanford.edu*💡