Pell's equation

Pell's equation is any Diophantine equation of the form

<math>x^2-ny^2=1<math>

where n is a nonsquare integer. In calling it "Diophantine" we are really saying what we intend to do with the equation rather than describing any intrinsic property of the equation: we intend to seek solutions in which both x and y are integers. Infinitely many such solutions of this equation exist. The solutions yield good rational approximations to the square root of the natural number n.

The name of this equation arose from Leonhard Euler's mistakenly attributing its study to John Pell. Euler was aware of the work of Lord Brouncker, the first European to find a general solution of the equation, but apparently confused Brouncker with Pell. In fact, this equation had been studied extensively by Indian mathematicians, starting with Brahmagupta about a thousand years before Pell's time, and subsequently by Bhaskara II in the 12th century, and later by Narayana in the 14th century.

As motivation, consider the square root of two. It is often approximated 1.414..., which some might incorrectly interpret as 1.41414141414..., or 140/99. Likewise, the reciprocal of the square root of two to three decimal places is 0.707, which is suggestive of 0.70707070..., or 70/99. If 70/99 approximates the reciprocal of the square root of two, it follows that 99/70 approximates the square root of two. As it turns out, the square root of two is between 140/99 and 99/70. The arithmetic mean of these two rationals is 19601/13860. That number squared is 384199201/192099600. It turns out that 2 times the denominator 192099600 is 384199200, which differs from the numerator by only one. p = 19601 and q = 13860 satisfies the Diophantine equation 2q² + 1 = p². Any fraction of natural numbers p and q that satisfy this equation will be a reasonably good approximation for the square root of two.

More generally, if n is a given natural number, then any fraction of natural numbers p and q that satisfy the Pell's equation

nq² + 1 = p²

is a reasonably good approximation for the square root of n. The larger the numbers p and q, the better the approximation.

It turns out that if both (a, b) and (c, d) satisfy a Pell's equation, then so do

<math>(bc + ad, bd + nac)<math>

and

<math>(bc - ad, bd - nac).<math>

Fermat proved that p and q can always be found to satisfy a Pell's equation for any natural number n that is not a perfect square. Given a computer with bignum capability, this makes it easy to converge rapidly toward any irrational square root of a n. As an added bonus, a Pell's equation can always be solved in a finite number of steps by calculating the continued fraction representation of the square root of n.

A general development of solutions of Pell's equation in terms of continued fractions can be presented, as these arise as a special case of quadratic irrationals. Gauss classified such solutions into 64 or 65 sets, with the precise classification of one or the other implying the truth or falsity of the Riemann hypothesis.

The relationship to the continued fractions implies that the solutions to Pell's equation form a semigroup subset of the modular group. Thus, for example, if p and q satisfy Pell's equation, then

<math>\begin{pmatrix} p & q \\ nq & p \end{pmatrix}<math>

is a matrix of unit determinant. Products of such matrices take exactly the same form, and thus all such products yield solutions to Pell's equation. This can be understood in part to arise from the fact that successive convergents of a continued fraction share the same property: If <math>p_{n-1}/q_{n-1}<math> and <math>p_{n}/q_{n}<math> are two successive convergents of a continued fraction, then the matrix

<math>\begin{pmatrix} p_{n-1} & p_{n} \\ q_{n-1} & q_{n} \end{pmatrix}<math>

has determinant +1 or -1.fr:Équation de Pell