Pell Equation

A special case of the quadratic Diophantine equation having the form

where is a nonsquare natural number (Dickson 2005). The equation

arising in the computation of fundamental units is sometimes also called the Pell equation (Dörrie 1965, Itô 1987), and Dörrie calls the positive form of (2) the Fermat difference equation. While Fermat deserves credit for being the first to extensively study the equation, the erroneous attribution to Pell was perpetrated by none other than Euler himself (Nagell 1951, p. 197; Burton 1989; Dickson 2005, p. 341). The Pell equation was also solved by the Indian mathematician Bhaskara. Pell equations are extremely important in number theory, and arise in the investigation of numbers which are figurate in more than one way, for example, simultaneously square and triangular.

The equation has an obvious generalization to the Pell-like equation

as well as the general second-order bivariate Diophantine equation

However, several different techniques are required to solve this equation for arbitrary values of , , and . The Wolfram Language command Reduce[f[x, y] && Element[x|y, Integers]] finds solutions to the general equation (4) when they exist.

Pell equations of the form (1), as well as certain cases of the analogous equation with a minus sign on the right,

can be solved by finding the continued fraction of . Note that although the equation (5) is solvable for only certain values of , the continued fraction technique provides solutions when they exist, and always in the case of (1), for which a solution always exists. A necessary condition that (5) be solvable is that all odd prime factors of be of the form , and that cannot be doubly even (i.e., divisible by 4). However, these conditions are not sufficient for a solution to exist, as demonstrated by the equation , which has no solutions in integers (Nagell 1951, pp. 201 and 204).

In all subsequent discussion, ignore the trivial solution , . Let denote the th convergent , then we will have solved (1) or (5) if we can find a convergent which obeys the identity

Amazingly, this turns out to always be possible as a result of the fact that the continued fraction of a quadratic surd always becomes periodic at some term , where , i.e.,

To compute the continued fraction convergents to , use the usual recurrence relations

where is the floor function. For reasons to be explained shortly, also compute the two additional quantities and defined by

Now, two important identities satisfied by continued fraction convergents are

(Beiler 1966, p. 262), so both linear

and quadratic

equations are solved simply by finding an appropriate continued fraction.

Let be the term at which the continued fraction becomes periodic (which will always happen for a quadratic surd). For the Pell equation

with odd, is positive and the solution in terms of smallest integers is and , where is the th convergent. If is even, then is negative, but

so the solution in smallest integers is , . Summarizing,

The equation

can be solved analogously to the equation with on the right side iff is even, but has no solution if is odd,

Given one solution (which can be found as above), a whole family of solutions can be found by taking each side to the th power,

Factoring gives

and

which gives the family of solutions

These solutions also hold for

except that can take on only odd values.

The following table gives the smallest integer solutions to the Pell equation with constant (Beiler 1966, p. 254). Square are not included, since they would result in an equation of the form

which has no solutions (since the difference of two squares cannot be 1).

The first few minimal values of and for nonsquare are 3, 2, 9, 5, 8, 3, 19, 10, 7, 649, ... (OEIS A033313) and 2, 1, 4, 2, 3, 1, 6, 3, 2, 180, ... (OEIS A033317), respectively. The values of having , 3, ... are 3, 2, 15, 6, 35, 12, 7, 5, 11, 30, ... (OEIS A033314) and the values of having , 2, ... are 3, 2, 7, 5, 23, 10, 47, 17, 79, 26, ... (OEIS A033318). Values of the incrementally largest minimal are 3, 9, 19, 649, 9801, 24335, 66249, ... (OEIS A033315) which occur at , 5, 10, 13, 29, 46, 53, 61, 109, 181, ... (OEIS A033316). Values of the incrementally largest minimal are 2, 4, 6, 180, 1820, 3588, 9100, 226153980, ... (OEIS A033319), which occur at , 5, 10, 13, 29, 46, 53, 61, ... (OEIS A033316).

The more complicated Pell-like equation

with has solution iff is one of the values for , 2, ..., computed in the process of finding the convergents to (where, as above, is the term at which the continued fraction becomes periodic). If , the procedure is significantly more complicated (Beiler 1966, p. 265; Dickson 2005, pp. 387-388) and is discussed by Gérardin (1910) and Chrystal (1961).

Regardless of how it is found, if a single solution , to (39) is known, other solutions can be found. Let and be solutions to (39), and and solutions to the "unit" form

Then the identity

allows larger solutions to the equation to be found by using incrementally larger values of the , which can be easily computed using the standard technique for the Pell equation. Such a family of solutions does not necessarily generate all solutions, however. For example, the equation

has three distinct sets of fundamental solutions, , (13, 4), and (57, 18). Using (42), these generate the solutions shown in the following table, from which the set of all solutions (7, 2), (13, 4), (57, 18), (253, 80), (487, 154), (2163, 684), (9607, 3038), ... can be generated.

The case

can be reduced to the one above by multiplying through by ,

finding solutions in , and then selecting those for which is an integer.

According to Dickson (2005, pp. 408 and 411), the equation

with , which has either no solutions or a finite number of solutions, was solved by Gauss in 1863 using the method of exclusions and considered by Euler (1773) and Nasimoff (1885), although Euler's methods were incomplete (Smith 1965; Dickson 2005, p. 378). According to Itô (1987), this equation can be solved completely using solutions to Pell's equation. Nasimoff (1885) applied Jacobi elliptic functions to express the number of solutions of this equation for odd (Dickson 2005, p. 411). Additional discussion including the connection with elliptic functions is given in Dickson (2005, pp. 387-391).

The special case of and prime was solved by Cornacchia (Cornacchia 1908, Cox 1989, Wagon 1990). A deterministic algorithm for finding all primitive solutions to (46) for fixed relatively prime integers, , and was given by Hardy et al. (1990). This algorithm generalizes those of Hermite (1848), Serret (1848), Brillhart (1972), Cornacchia (1908), and Wilker (1980). It requires factorization of , and has worst case running time of , independent of and . An algorithmic method for finding all solutions is implemented in the Wolfram Language as Reduce[x^2 + d y^2 == n, x, y, Integers].