How to Solve the Pell Equation
The relation X2 - nY2 = 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 (X1, Y1). The fundamental solution depends on the value of n. The solutions form an increasing sequence {(Xk, Yk)} in which the ratio Xk/Yk 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 X2 - 2Y2 = 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 X2 - 2Y2 = 1 are
(X1, Y1) = (3, 2)
(X2, Y2) = (17, 12)
(X3, Y3) = (99, 70)
(X4, Y4) = (577, 408)
(X5, Y5) = (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 X2 - nY2 = 1
The pair (1, 0) is always a trivial solution to Pell's equation for each n. The smallest non-trivial solution to X2 - nY2 = 1 is called the fundamental solution. If you know the fundamental solution (a, b), then you can find all solutions with the coupled recurrence formulasXk+1 = aXk + nbYk
Yk+1 = bXk + aYk,
Which can be simplified to Xk+2 = 2aXk+1 - Xk and Yk+2 = 2aYk+1 - Yk, where X0 = 1, X1 = a, Y0 = 0, and Y1 = b.
Using the relation a2 - 1 = nb2, the explicit formulas for Xk and Yk are
Xk = 0.5*(a + b*sqrt(n))k + 0.5*(a - b*sqrt(n))k
Yk = (1/2sqrt(n))*(a + b*sqrt(n))k - (1/2sqrt(n))*(a - b*sqrt(n))k
Finding the Fundamental Solution of X2 - nY2 = 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 X1 and the denominator is Y1.
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 X2 - 23Y2 = 1.
© Had2Know 2010