Offtonic Pell Solver has been released!

(Part 1)

We’re solving x^2 – Dy^2 = N. We’ve gotten the very easy cases out of the way: N = 0, D = 0. We’ve gotten the easy cases out of the way: D < 0, D = d^2. This leaves only the situation where D is a non-square positive integer and N is nonzero. As we will see, this one is legitimately complicated. A Pell equation is one where N = 1. Such an equation always has a solution. Now let’s suppose (x,y) is a solution to x^2 – Dy^2 = N and (r,s) is a solution to x^2 – Dy^2 = 1. If u + v sqrt(D) = (r + s sqrt(D))(x + y sqrt(D)), (u,v) will also be a solution to x^2 – Dy^2 = N. In other words, you can combine a solution of the original equation with a solution to the N = 1 equation to create a new solution of the original equation. And you can do this forever: if a solution exists, there is an infinite number of them. Luckily, it turns out that those infinite solutions are organized: there is a finite number of fundamental solutions, and each of those can generate an infinity of solutions by combining with the N = 1 solution. Our task, then, is to (a) find the N = 1 solution (the N = -1 solution is important as well, if it exists), (b) find the fundamental solutions, and (c) combine them. We can do (c) very easily using the formula above; the challenges are (a) and (b). But first, there’s an algorithm called the PQa algorithm, and there are various equivalent formulations of it. The one I will show is the one from John P. Robertson’s paper: