### Solving Pell's equation without irrational numbers

The algorithm is due to Norman J. Wildberger at J. Integer Sequences, Vol. 13 (2010) 10.4.3. The BCMATH version is based on the BC version.
Here D > 1 is a nonsquare integer. We construct matrices A_{k} = with a_{k} > 0 > c_{k} with b_{k}^{2} - a_{k}c_{k} = D and unimodular matrices N_{k}, k ≥ 0.

Starting with A_{0} = and N_{0} = I_{0}, and N_{k} = M_{1} ⋯ M_{k} if k ≥ 1, where M_{i} = L = or R = and M_{1} = R,
we choose M_{k+1} = R if a_{k} + 2b_{k} + c_{k} < 0, and choose M_{k+1} = L if a_{k} + 2b_{k} + c_{k} > 0.
We have N_{k}^{t}A_{0}N_{k} = A_{k} for k ≥ 0.

For some n > 0, N_{n}^{t}A_{0}N_{n}=A_{0}, where N_{n} is a positive matrix of the form and (u,v) is the least positive solution of Pell's equation. In the factorization of N_{n}, the M_{i} form a palindromic sequence.

The negative Pell equation will be soluble if and only if there exists a k such that A_{k} = , in which case, A_{k} will be at the centre of symmetry and N_{k} will have the form . Then (u, v) = (u_{1}^{2} + Dv_{1}^{2}, 2u_{1}v_{1}) and (u_{1}, v_{1}) will be the least positive solution of the negative Pell equation.

Note that in Wildberger's paper, on page 7, the equation N = MM^{t} is not correct and should be replaced by N = MM^{+}, where M^{+} = .

Wildberger does not prove that the solutions found are the least positive solutions, but this can be demonstrated by considering George Raney's L-R factorization algorithm applied to matrices and , where x^{2} - Dy^{2} = 1 and x_{1}^{2} - Dy_{1}^{2} = 1.

E = 0 prints the least positive solution of Pell's equation x^{2} - Dy^{2} = 1 and
determines in the negative Pell equation x^{2} - Dy^{2} = -1 is soluble, in which case the least positive solution is found.

*Last modified 21st February 2015*

Return to main page