Friday, November 04, 2005

Pell's Equation

Despite its name, Pell's Equation has nothing to do with the British mathematician John Pell. The problem was wrongly attributed to Pell by Leonard Euler in a very influencial work that Euler wrote when he was still in his 20s. Despite Euler's mistake (apparently, he had meant to cite Viscount William Brouncker), Pell's name stuck. Interestingly, according to Harold M. Edwards, there is a very good chance that Brouncker also wasn't involved with the problem. The work on the British side may have been done by John Wallis who cited Brouncker as an effort to gain favor with the viscount.

It was Pierre de Fermat who brought Europe's math community to focus on this equation in 1657 when he posed the problem as a challenge to the British mathematicians. Fermat was not the first to identify the problem. Diophantus studied one variant of Pell's equation and a famous problem by Archimedes known as the Cattle Problem can be stated in terms of Pell's equation. Great progress in solving Pell's equation were made by Indian mathematicians by Brahmagupta (born in 598 AD) and Bhascara Acharya (born in 1114 AD).

Pell's equation amounts to this:

Find all integer solutions for x,y where Ax2 + 1 = y2.

Interestingly, when this problem got passed on to the English, the part about "integers" was dropped and the British mathematicians quickly found a solution for rational solutions.

Here's the solution in terms of rational values:

Lemma: There are an infinite number of rational solutions to Ax2 + 1 = y2 where x,y are rational numbers.

(1) Let m = y-1, n = x. Then we know that: (y -1)/x = m/n and y-1 = (m/n)x and y = 1 + (m/n)x.

(2) So, Ax2 + 1 = [1 + (m/n)x]2 = 1 + 2(m/n)x + (m2/n2)x2

(3) Multiplying n2 to both sides gives us:

An2x2 + n2 = n2 + 2mnx + m2x2

An2x2 = 2mnx + m2x2

An2x2 - m2x2 = 2mnx

(4) Dividing x from both sides gives us:

An2x - m2x = 2mn = x(An2 - m2)

So that:
x = 2mn/(An2 - m2)

y = 1 + (m/n)x = 1 + (m/n)(2mn/[An2 - m2]) =1 + 2m2/(An2 - m2) = (An2 - m2 + 2m2)/(An2 - m2) = (An2 + m2)/(An2 - m2)


When Fermat saw the solution for rational values, he rejected it explaining that it was ridiculous to think that he would offer a problem as simple as this. He clarified that the problem is only interesting when the solution is for integers.

The British mathematicians at first responded that Fermat's new problem was artificial. They saw little justification for solving the problem specifically for whole numbers when the solution for rational values was valid. Later, an integer solution and a method for finding solutions was put forward without any proof that the method worked in all circumstances. Historically, Lord Brouncker is given credit for the solution.

The verification of the British method would have to wait over 100 years. It was the great mathematician Joseph-Louis Lagrange, using continued fractions, who showed that the British method worked in all circumstances. Go here to see how continued fractions can be used to provide a solution to Pell's equation.



Scouse Rob said...

In Step(3), last line:
An^2 - m^2x^2 = 2mnx
Should be:
An^2x^2 - m^2x^2 = 2mnx ?


Larry Freeman said...

Hi Rob,

Thanks for noticing. I fixed the typo.