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

  • Thread starter mrdex
  • Start date
In summary, the program finds the minimal values of x and y where x/y=[a_{0}, a_{1}, \ldots, a_{k}, 2a_{0}, a_{1}, \ldots, a_{k}].
  • #1
mrdex
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 achieve but they don't mention how those values in the table were found. Any ideas?
 
Physics news on Phys.org
  • #2
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
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
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
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
Ok thanks very much shmoe. I should be able to figure it out from there :smile:.
 
  • #7
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
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
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
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
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 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 [tex] Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0 [/tex] (click on 'methods') but has also a good calculator.
 

1. What is Pell's equation?

Pell's equation is a type of mathematical equation in the form of x^2 - dy^2 = 1, where d is a positive non-perfect square. It is named after the mathematician John Pell who studied it in the 17th century.

2. How do you solve Pell's equation?

The general method for solving Pell's equation is to find the continued fraction representation of the square root of d, then use that to find the smallest positive integer solution (x, y) that satisfies the equation.

3. Are there any special cases or exceptions when solving Pell's equation?

Yes, there are a few special cases when solving Pell's equation. For example, if d is a perfect square, there are no positive integer solutions. If d is a negative integer, there are infinitely many solutions.

4. Can Pell's equation be solved for all values of d?

No, Pell's equation cannot be solved for all values of d. There are certain values of d for which there are no integer solutions, such as when d is a perfect square or when d is congruent to 2 or 3 modulo 4.

5. What are some applications of Pell's equation?

Pell's equation has applications in number theory, particularly in the study of quadratic diophantine equations. It has also been used in cryptography, specifically in the development of the RSA algorithm. Additionally, it has been used in solving certain types of exponential Diophantine equations and in finding integer solutions to certain polynomial equations.

Similar threads

  • Linear and Abstract Algebra
Replies
11
Views
5K
  • Computing and Technology
Replies
20
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
2K
Replies
1
Views
813
  • Differential Equations
Replies
2
Views
917
Replies
17
Views
2K
  • Linear and Abstract Algebra
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
11
Views
689
  • Calculus and Beyond Homework Help
Replies
10
Views
409
  • Science and Math Textbooks
Replies
5
Views
2K
Back
Top