Pell Equation

A Pell equation is a special case of the quadratic Diophantine equation having the form

where and are integers and is a nonsquare positive integer (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 a square number and a triangular number.

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

as well as the general second-order bivariate Diophantine equation

Several different techniques are required to solve this equation for arbitrary integer values of , , , , , and . For a polynomial , the Wolfram Language command Reduce[F[x, y] == 0, x, y, Integers] finds the integer solutions of .

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).

For the equations with right-hand side , the following construction gives solutions in positive integers. The solutions with to the positive equation are . Let denote the th convergent , then we will have solved (1) or (5) if we can find a convergent which obeys the identity

The periodic continued fraction of has a repeating block beginning at and ending at , with period , i.e.,

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

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

The recurrence relations for and apply for , and the formula for applies for . Two important identities satisfied by continued fraction convergents for are

(Beiler 1966, p. 262). A linear equation

with relatively prime positive integers and can be solved using the continued fraction of . Quadratic equations

can be solved using the continued fraction of in the cases described below.

Let be the last term of the repeating block of the continued fraction of . 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 a solution with to the equation with right-hand side 1, a family of solutions is obtained by taking powers of , for positive integers ,

Factoring gives

and

which gives the family of solutions

When instead solves the negative equation, the same formulas give solutions of

for odd . Even powers give solutions of the equation with right-hand side 1.

The following table gives the smallest positive 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 solution with , since two distinct positive squares cannot differ by 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 least values of for which the minimal is 2, 3, ... are 3, 2, 15, 6, 35, 12, 7, 5, 11, 30, ... (OEIS A033314) and the least values of for which the minimal is 1, 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 a relatively prime positive integer solution iff is one of the values for , 2, ..., . This range includes the endpoints of two periods of the periodic continued fraction. Without the relatively prime restriction, a positive integer solution exists iff for a positive integer and an index in the same range. For every positive solution, and are the numerator and denominator of some convergent, where is the greatest common divisor of and (Conrad, §5). 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 sequences of positive solutions beginning with , (13,4), and (57,18). Multiplication by gives the recurrence relation and generates the solutions shown in the following table. Together these sequences give all positive solutions (7, 2), (13, 4), (57, 18), (253, 80), (487, 154), (2163, 684), (9607, 3038), ....

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 solutions to (46) in relatively prime positive integers and , for fixed positive integers , , and with , , 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 algorithm for finding all solutions is implemented in the Wolfram Language as Reduce[x^2 + d y^2 == n, x, y, Integers].