Continued Fractions and the Pell Equation

Recently in class we lightly touched on the subject of continued fractions, and it brought back memories of a class I took last semester on Number Theory. I thoroughly enjoyed the class and a section I enjoyed more than any other was on the Pell Equation. This equation, of the form x2-Dy2=1, is a Diophantine equation, a polynomial equation with more than one variable, named after Diophantus of Alexandria. The equation was first studied by the Indian mathematician Brahmagupta, although he never gave a general solution, rather he used specific examples. The first person to provide a general solution was Lord Brouncker; however, Euler attributed the solution to John Pell, most likely because he confused Pell with Brouncker. The Pell Equation can be used as an approximation of the square root of non-square numbers. When D=11, a solution of that particular Pell equation (in this case, the first integer solution) is (10,3). 10/3=3.333 repeating and √11 is just over 3.1.

The D=2 Pell Equation graphed. Where the function intersects a point where x and y are integers represents an integer solution. Image: David Eppstein, via Wikimedia Commons.

The method I use to solve the Pell Equation relies completely on continued fractions, specifically by writing √D as a continued fraction; this was primarily how Lord Brouncker found a solution. A continued fraction is the sum of a fraction within a fraction within a fraction. What is interesting is that all numbers can be written as continuous fractions. Rational fractions always terminate, while irrational fractions can continue forever or enter a periodic cycle. An example of a continued fraction is:

contf

Our fraction will have the form:

floor

and we will shortly define all of the α that appear. The fraction above also has a floor function. The floor is defined as the highest integer component of a number. A couple examples of this are floor(3.5)=3 and floor(√2)=1.

Continued fraction of √2, which has period p=1. Image: Zahnradzacken, via Wikimedia Commons.

Continued fraction of √2, which has period p=1. Image: Zahnradzacken, via Wikimedia Commons.

To tackle the Pell Equation it is necessary to define α and β. The first is α=√D+floor(√D)=, and the second is β=α-floor(α)=√D-floor(√D), which is equivalent to α=floor(α)+β . The method using continued fractions is recursive such that αn+1=(1/βn) and βnn-1. The reason why D must be a non-square number is that the square root of a non-square integer number will have a non-terminating periodic continued fraction. If D were a square number, β=√(square)-floor(√square)=0 as it becomes a whole number minus the floor of that same whole number. The periodic fraction will need to be truncated at a certain point, and that point is when the bottom denominator is equal to the original α.

Now the calculations can begin. For simplicity I am selecting D=3. α=√3+1 and

β=√3-floor(√3)=√3-1. The first step is to calculate the period of our fraction, that is find all αn.

α1=1/β=1/(√3-1) then multiply the top and bottom by the conjugate √3+1 which will give:

α1=(√3+1)/2=/=α. (floor(α1)=1) Then calculate β11-1=(√3-1)/2

α2=1/β1=2/(√3-1)=√3+1=α, thus D=3 has period p=2.

The continued fraction is:

root3

When working backwards to calculate √3 as a fraction with only one denominator, the fraction comes out the be (2√3+3)/(1√3+2). Then it can be claimed that this can be written as:

D=(a√D+Dc)/(c√D+a) and we can compose a 2×2 matrix [a,Dc][c,a] and the determinant is:

a2-Dc2 (which looks a lot like the original equation). If you take a=2 and c=1, and substitute them in for x and y, you get 22-3*12=4-3*1=4-3=1 Thus (x,y)=(2,1) is the first solution to x2-3y2=1

One more interesting thing we can do with periodic continued fractions is, given such a fraction, we can find D and then find the solution to the equation. An example would be

α=6+1/(3+1/(6+1/…))) where 3 and 6 alternate. Because of the periodic nature of the fraction, it can be rewritten as α=6+1/(3+1/α)). Solving for alpha, the equation becomes

2+α=19α+6, then 3α2-18α=6, and if we divide by 3 and add 9 to both sides to complete the square we get (α-3)2=11, thus this is the continued fraction of √11. Because the continued fraction was given at the beginning, α=√11+3 can be plugged into it and use the same process as D=3 to get the first solution to the equation x2-11y2=1, which happens to be (x,y)=(10,3).

There are a few little quirks that really interest me about the Pell Equation. What might be considered intuitive is that if D=n2-1, then x=n and y=1. Another quirk is just how large first solutions can become. When D=61, the smallest solution (x,y)=(17663190049,226135980), yet when D=63, (x,y)=(8,1). Another quirk solution is (x,y)=(1,0), as it is true for any D.

The Pell Equation is, at least to me, an equation that is beautiful because it looks so simple and yet has some surprising methods to solve it and has a wide range of solutions. It relies upon periodic continued fractions and numerical methods to solve and has so far been my favorite problems to work on.

Sources:

http://www.math.utah.edu/~hacon/4400/Savin-book08_jun.pdf

http://www-history.mcs.st-and.ac.uk/history/HistTopics/Pell.html#s205

http://en.wikipedia.org/wiki/Continued_fraction

http://mathworld.wolfram.com/PellEquation.html

http://en.wikipedia.org/wiki/Pell%27s_equation

http://en.wikipedia.org/wiki/Brahmagupta

http://www.codecogs.com/latex/eqneditor.php (Used for generating equation images)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s