How to Solve the Pell Equation

The relation X² - nY² = 1, where X, Y, and n are positive integers is called the Pell Equation (or Pell's Equation). It was extensively studied by the Indian mathematician Brahmagupta in the 7th century, and later by the English mathematician Viscount Brouncker in the 17th century. Euler erroneously attributed it to another English mathematician, John Pell, and the name has since stuck.

When n is non-square, Pell's Equation has infinitely many solution pairs (X, Y), all of which can be generated by a single fundamental solution (X₁, Y₁). The fundamental solution depends on the value of n. The solutions form an increasing sequence {(X_k, Y_k)} in which the ratio X_k/Y_k is a close approximation to sqrt(n). As k grows, the approximation becomes more accurate.

Example

Greek mathematicians were particularly interested in the case when n = 2, the equation X² - 2Y² = 1. Solutions to this equation can be used to find rational approximations of sqrt(2). The equation also arises when searching for instances of Pythagorean triples in which the legs differ by 1, that is, Pythagorean triangles that are close to being isosceles right triangles.

The first few solutions of X² - 2Y² = 1 are

(X₁, Y₁) = (3, 2)
(X₂, Y₂) = (17, 12)
(X₃, Y₃) = (99, 70)
(X₄, Y₄) = (577, 408)
(X₅, Y₅) = (3363, 2378)

Notice that 3/2 = 1.5, 17/12 = 1.416, 99/70 = 1.4142857, etc. Each successive ratio is closer to sqrt(2) = 1.414213...

If you add the values of X and Y in each pair, you obtain the hypotenuse of a Pythagorean triple in which the legs differ by 1:

(3, 2) → (3, 4, 5)
(17, 12) → (20, 21, 29)
(99, 70) → (119, 120, 169)
(577, 408) → (696, 697, 985)
(3363, 2778) → (4059, 4060, 5741)

Finding All Solutions of X² - nY² = 1

The pair (1, 0) is always a trivial solution to Pell's equation for each n. The smallest non-trivial solution to X² - nY² = 1 is called the fundamental solution. If you know the fundamental solution (a, b), then you can find all solutions with the coupled recurrence formulas

X_k+1 = aX_k + nbY_k
Y_k+1 = bX_k + aY_k,

Which can be simplified to X_k+2 = 2aX_k+1 - X_k and Y_k+2 = 2aY_k+1 - Y_k, where X₀ = 1, X₁ = a, Y₀ = 0, and Y₁ = b.

Using the relation a² - 1 = nb², the explicit formulas for X_k and Y_k are

X_k = 0.5*(a + b*sqrt(n))^k + 0.5*(a - b*sqrt(n))^k
Y_k = (1/2sqrt(n))*(a + b*sqrt(n))^k - (1/2sqrt(n))*(a - b*sqrt(n))^k

Finding the Fundamental Solution of X² - nY² = 1

The challenge of Pell's equation is in finding the fundamental solution. Once it is known, all other solutions can be obtained. Unfortunately, there is no closed form expression (A(n), B(n)) that gives the fundamental solution as a function of n.

However, you can find the fundamental solution by running one of the many known algorithms. The continued fraction algorithm developed by Brounker is one of the most straightforward methods.

To apply this method to solve Pell's equation, you simply compute the continued fraction of sqrt(n) and stop when the expansion begins to repeat. Then calculate the convergent fraction of the first cycle excluding the last element in the cycle. The numerator of the fraction is X₁ and the denominator is Y₁.

Example: The continued fraction of sqrt(23) is

4 + ¹/₁₊ ¹/₃₊ ¹/₁₊ ¹/₈₊ ...

which repeats after a cycle of length 4. The first convergent fraction excluding the last term (8) is

4 + 1/(1 + 1/(3 + 1/1)) = 24/5.

Thus, (24, 5) is the fundamental solution of X² - 23Y² = 1.

© Had2Know 2010