# How to Solve the Pell Equation

The relation X^{2} - nY^{2} = 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_{1}, Y_{1}). 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^{2}- 2Y

^{2}= 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

^{2}- 2Y

^{2}= 1 are

(X

_{1}, Y

_{1}) = (3, 2)

(X

_{2}, Y

_{2}) = (17, 12)

(X

_{3}, Y

_{3}) = (99, 70)

(X

_{4}, Y

_{4}) = (577, 408)

(X

_{5}, Y

_{5}) = (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^{2} - nY^{2} = 1

The pair (1, 0) is always a trivial solution to Pell's equation for each n. The smallest non-trivial solution to X^{2}- nY

^{2}= 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

_{0}= 1, X

_{1}= a, Y

_{0}= 0, and Y

_{1}= b.

Using the relation a

^{2}- 1 = nb

^{2}, 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^{2} - nY^{2} = 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

_{1}and the denominator is Y

_{1}.

**Example:**The continued fraction of sqrt(23) is

4 +

^{1}/

_{1+}

^{1}/

_{3+}

^{1}/

_{1+}

^{1}/

_{8+}...

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

^{2}- 23Y

^{2}= 1.

© *Had2Know 2010
*