How to solve Pell's equation using Alpertron's online calculator

[mrdex]

Ok, I've done a lot of searching and looking around but I cannot find anything that I can make sense of. The Pell equation I want to solve is this:

x^2 - Dy^2 = 1

Given an integral value for D that is not a square number, find the minimal values of x and y where x and y are both integers.

I've seen stuff about using continued fractions or finding values for x and y once given the minimal values of x and y but I can't make head nor tale of it all. The Mathworld page on Pell equations gives a lot of information but most of it is irrelevant. Near the bottom they show a table of the results I want to achieve but they don't mention how those values in the table were found. Any ideas?

 

[Gokul43201]

what do you mean by minimal ? I don't know a whole lot about this, but I'm guessing you are looking for positive integer solutions.

Else the minimal solution is (1,0) for all D...but I think that's not what you want !

 

[Gokul43201]

Also, it looks like x/y near sqrt(D), gives you x,y for all the cases I tried (7 or 8). So looking for rational approximations to sqrt(D) may be the way to go. Perhaps, that's where the continued fractions come in.

D=2, sqrt(D) = 1.4142... x/y=3/2 = 1.5
D=3, sqrt(D) = 1.732 ... x/y=7/4 = 1.75
D=5, sqrt(D) = 2.24 ... x/y = 9/4 = 2.25
etc.

 

[shmoe]

Hi, you'll have to learn how to calculate square roots with continued fractions.

Since formatting continued fractions is a nightmare of parentheses, I'll refer you to http://mathworld.wolfram.com/ContinuedFraction.html and ask you to read equation (3), which gives the basic form of the continued fractions we'll need and the shortcut form for this (4) so I don't scratch my eyeballs out trying to format things. Also see (11) for the finite version of this. Another bit of slightly confusing notation, [x] will mean the greatest integer less than x. This shouldn't be confused with our continued fraction notation, since that will always have more than one term.

Assume D is not a perfect square. To find the continued fraction expression of \sqrt{D}, we first set a_{0}=[\sqrt{D}]. This is a very crude approximation to \sqrt{D}. At this point we have \sqrt{D}=a_{0}+(\sqrt{D}-a_{0})=a_{0}+\frac{1}{\frac{1}{\sqrt{D}-a_{0}}}

We apply the same procedure to \frac{1}{\sqrt{D}-a_{0}}=\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}} and get a_{1}=[\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}}]

Now we have \sqrt{D}=a_{0}+\frac{1}{a_{1}+(\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}}-a_{1})}

Now a_{2}=[\frac{1}{\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}}-a_{1}}]. Continue to get the rest of the a's. Eventually you'll get something that repeats like \sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}]

Heres where you stop. If k is odd find integers x and y where x/y=[a_{0}, a_{1}, \ldots, a_{k}]. These are your minimal solutions to Pell's equation. If k is even, you do something similar, I'm not positive exactly what, sorry. I'll hopefully come back tomorrow with an answer.

An example: D=14

a_{0}=[\sqrt{14}]=3 so \sqrt{14}=3+\frac{1}{\frac{1}{\sqrt{14}-3}}

a_{1}=[\frac{1}{\sqrt{14}-3}]=[\frac{\sqrt{14}+3}{5}]=1

So \sqrt{14}=3+\frac{1}{1+(\frac{\sqrt{14}+3}{5}-1)}=3+\frac{1}{1+\frac{1}{\frac{1}{\frac{\sqrt{14}+3}{5}-1}}}

a_{2}=[\frac{1}{\frac{\sqrt{14}+3}{5}-1}]=[\frac{5}{\sqrt{14}-2}]=[\frac{\sqrt{14}+2}{2}]=2

So
\sqrt{14}=3+\frac{1}{1+\frac{1}{2+(\frac{\sqrt{14}+2}{2}-2)}}

ok I'm stopping here. Go a couple more steps and you'll get \sqrt{14}=[3,1,2,1,3+\sqrt{14}], so we've started to repeat.

Now find [3,1,2,1]=3+\frac{1}{1+\frac{1}{2+\frac{1}{1}}}=15/4, so x=15 and y=4 are the minimal solutions in this case.

 

[shmoe]

I figured out what to do when k is even. I knew it involved doubling the period or something similar, but it wasn't working out. Sorry for the confusion.

Anyhoo, ionce you get to \sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}] and k is even, you need to find x, y with x/y=[a_{0}, a_{1}, \ldots, a_{k}, 2a_{0}, a_{1}, \ldots, a_{k}], then x, y are your minimal solutions.

The 2a_{0} term shouldn't be suprising. If you were at \sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}], and you wanted to find more terms, you'd see a_{k+1}=2a_{0}. Muck about with a few examples and you'll see why this is so.

 

[mrdex]

Ok thanks very much shmoe. I should be able to figure it out from there .

 

[shmoe]

You're welcome . Feel free to ask any questions if you need clarification. Also, if you want details on how to generate all solutions from the minimal one, just ask.

 

[mrdex]

Just to let you know that I managed to make a program which finds the minimum values of x and y given a value of D thanks to your explanation. I would definatley have gotten stuck on the if k is even thing. I still don't understand why it should make a difference. Anyway thanks again .

 

[shmoe]

Glad it worked for you.

If you truncate after the first period you get (-1)^{k+1}.

If you try D=10, you'll get [3,3+\sqrt{10}]. If you take x/y=3/1 then you get

3^2-10\cdot 1^2=-1

but if you go to x/y=[3,6]=3+1/6=19/6, you get:

19^2-10\cdot 6^2=1

Notice (3+\sqrt{10})(3+\sqrt{10})=19+6\sqrt{10}, this is no accident! You can get the rest of the solutions to Pell's either by finding more periods of your continued fraction or by finding powers of your minimal solution.

 

[robert Ihnot]

Here is a nice problem, within reach of a programmable calculator too.

X^2-97Y^2=-1.

Hint:.. here is the expansion,

{9,1,5,1,1,1,1,1,1,5,1,(18)}

 

[metacristi]

Ok, I've done a lot of searching and looking around but I cannot find anything that I can make sense of. The Pell equation I want to solve is this:

x^2 - Dy^2 = 1

Given an integral value for D that is not a square number, find the minimal values of x and y where x and y are both integers.

I've seen stuff about using continued fractions or finding values for x and y once given the minimal values of x and y but I can't make head nor tale of it all. The Mathworld page on Pell equations gives a lot of information but most of it is irrelevant. Near the bottom they show a table of the results I want to achieve but they don't mention how those values in the table were found. Any ideas?

Try http://www.alpertron.com.ar/QUAD.HTM

It noy only presents a general method of solving Diophantine equations Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 (click on 'methods') but has also a good calculator.