How to solve Pell's equation

  • Thread starter mrdex
  • Start date
  • #1
5
0
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:

[tex] x^2 - Dy^2 = 1 [/tex]

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 acheive but they don't mention how those values in the table were found. Any ideas?
 

Answers and Replies

  • #2
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
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 !
 
  • #3
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,051
18
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.
 
  • #4
shmoe
Science Advisor
Homework Helper
1,992
1
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 [tex]\sqrt{D}[/tex], we first set [tex]a_{0}=[\sqrt{D}][/tex]. This is a very crude approximation to [tex]\sqrt{D}[/tex]. At this point we have [tex]\sqrt{D}=a_{0}+(\sqrt{D}-a_{0})=a_{0}+\frac{1}{\frac{1}{\sqrt{D}-a_{0}}}[/tex]

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

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

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

Heres where you stop. If k is odd find integers x and y where [tex]x/y=[a_{0}, a_{1}, \ldots, a_{k}][/tex]. 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

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

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

So [tex]\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}}}[/tex]

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

So
[tex]\sqrt{14}=3+\frac{1}{1+\frac{1}{2+(\frac{\sqrt{14}+2}{2}-2)}}[/tex]

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

Now find [tex][3,1,2,1]=3+\frac{1}{1+\frac{1}{2+\frac{1}{1}}}=15/4[/tex], so x=15 and y=4 are the minimal solutions in this case.
 
Last edited:
  • #5
shmoe
Science Advisor
Homework Helper
1,992
1
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 [tex]\sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}][/tex] and k is even, you need to find x, y with [tex]x/y=[a_{0}, a_{1}, \ldots, a_{k}, 2a_{0}, a_{1}, \ldots, a_{k}][/tex], then x, y are your minimal solutions.

The [tex]2a_{0}[/tex] term shouldn't be suprising. If you were at [tex]\sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}][/tex], and you wanted to find more terms, you'd see [tex]a_{k+1}=2a_{0}[/tex]. Muck about with a few examples and you'll see why this is so.
 
  • #6
5
0
Ok thanks very much shmoe. I should be able to figure it out from there :smile:.
 
  • #7
shmoe
Science Advisor
Homework Helper
1,992
1
You're welcome :smile: . 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.
 
  • #8
5
0
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 :smile:.
 
  • #9
shmoe
Science Advisor
Homework Helper
1,992
1
Glad it worked for you.

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

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

[tex]3^2-10\cdot 1^2=-1[/tex]

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

[tex]19^2-10\cdot 6^2=1[/tex]

Notice [tex](3+\sqrt{10})(3+\sqrt{10})=19+6\sqrt{10}[/tex], 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.
 
Last edited:
  • #10
1,056
0
Here is a nice problem, within reach of a programmable calculator too.

[tex] X^2-97Y^2=-1.[/tex]

Hint:.. here is the expansion,

{9,1,5,1,1,1,1,1,1,5,1,(18)}
 
Last edited:
  • #11
252
1
mrdex said:
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:

[tex] x^2 - Dy^2 = 1 [/tex]

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 acheive 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 [tex] Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 [/tex] (click on 'methods') but has also a good calculator.
 

Related Threads on How to solve Pell's equation

Replies
14
Views
9K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
6
Views
5K
  • Last Post
Replies
6
Views
4K
  • Last Post
Replies
10
Views
3K
Replies
15
Views
3K
  • Last Post
Replies
11
Views
5K
Top