How to find all solutions of Pell equation (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

can anyone tell me how i can get all the solutions of Pell's equation from the minimal solutions. the equation i want to solve is of the form:
x^2 - P*y^2 = 1

i can find the minimal solutions, e.g., the minimal solutions of the equation
x^2 - 2*y^2 = 1 are x = 3 and y = 2. how can i get the other solutions from these solutions?
 
Last edited:

Zurtex

Science Advisor
Homework Helper
1,120
1
I would just use a continued fraction expansion on the square root of P where the equation is: x2 - Py2 = a

What exactly do you know to do so far?
 
Well, what we do here is to look at the fundamental solution.

Take 1^2-2(1)^2 = -1, where we have the simplist case. We split this up: [tex](1-\sqrt2)
(1+\sqrt2)=-1 [/tex] It is obvious that raising these factors to any power produces only a product of -1.

Now take another solution X^2-2Y^2 = +/-1. Multiply these together:

[tex](1-\sqrt{2})(X-\sqrt{2}Y)= (X+2Y)-\sqrt2(X+Y)[/tex]

The first solution was X=1,Y=1, the general formula to follow is [tex]X_2=X+2Y; Y_2=X+Y. [/tex]

Thus solution sets are: (1,1); (3,2); (7,5); (17,12)......

Note here that -1 is possible for values of 2, 5, 13... that is, 2 and all primes of the form 4k+1, other than that for primes, we only have a solution for the value +1.
 
Last edited:
Zurtex said:
I would just use a continued fraction expansion on the square root of P where the equation is: x2 - Py2 = a

What exactly do you know to do so far?

the equation i want to solve is of the form:
x2 - Py2 = 1

i can find the minimal solutions, e.g., the minimal solutions of the equation
x2 - 2y2 = 1 are x = 3 and y = 2. how can i get the other solutions from these solutions?
 

shmoe

Science Advisor
Homework Helper
1,993
1
Again, you can factor your equation as [tex](3+2\sqrt{2})(3-2\sqrt{2})=1[/tex]. Get more solutions by finding powers of [tex](3+2\sqrt{2})[/tex]. e.g. [tex](3+2\sqrt{2})^2=(17+12\sqrt{2})[/tex], check that x=17, y=12 is a solution. This just comes from the norm on [tex]\mathbb{Z}[\sqrt{2}][/tex] being a multiplicative function. That you'll get all solutions from the fundamental one comes from Dirichlet's unit theorem for this ring.
 

Zurtex

Science Advisor
Homework Helper
1,120
1
If you understand the above I won't bother explaining the method of continued fraction expansion. However if you don't get it and you understand a bit about continued fraction expansions, just say so and I'll explain how you work it out that way.
 
Zurtex said:
If you understand the above I won't bother explaining the method of continued fraction expansion. However if you don't get it and you understand a bit about continued fraction expansions, just say so and I'll explain how you work it out that way.
Zurtex,
i understand a bit about continued fraction expansions (cfe), i.e., i know how to get the cfe of an integer. but i still don't understand what shmoe said. so i'd really be grateful if you could explain a bit.

thanks in advance.
 

Zurtex

Science Advisor
Homework Helper
1,120
1
Well all where D is a non square number it always true that:

[tex]\begin{multline*}
\sqrt{D} = \\
a_0 + \left(\frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots + \frac{1}{a_n + \frac{1}{a_1 + \frac{1}{\ddots}}}}}}\right)
\end{multline*}[/tex]

This is more simply expressed as:

[tex]\sqrt{D} = [a_0; a_1, a_2, \ldots, a_n, a_1, a_2, \ldots] = [a_0; \overline{a_1, a_2, \ldots, a_n}][/tex]

Now, if you don't mind, I'd rather not explain in general how to solve the equation x2 - Dy2 = c, as the methods split in to several cases depending on the value of c and the value of D. But the general method is about taking the CFE of the square root of D.

Lets just look at your case:

[tex]\sqrt{2} = [1; 2, 2, 2, \ldots] = [1; \overline{2}][/tex]

To cut a long story short, your solutions for x and y, where x and y are co-primes are:

[tex]\frac{x}{y} = [1; 2] = 1 + \frac{1}{2} = \frac{3}{2}[/tex]

So x = 3 and y = 2 is a solution.

[tex]\frac{x}{y} = [1;2,2,2] = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12}[/tex]

So x = 17 and y = 12 is a solution.

[tex]\frac{x}{y} = [1;2,2,2,2,2] = \frac{99}{70}[/tex]

So x = 99 and y = 70 is a solution.

I think you get the idea from there on :smile:. I'm sure if you search the internet you can find a good explanation of the general way of tackling this. I'm going to try and write up all my notes on to a wiki book at some point so I'll give the link out when I do.
 
Zurtex: I think you get the idea from there on . I'm sure if you search the internet you can find a good explanation of the general way of tackling this.

Yeah, and the reason he is taking two at a time with the continued fraction terms is because the simplest solution is for -1, not for 1.
 

Zurtex

Science Advisor
Homework Helper
1,120
1
robert Ihnot said:
Zurtex: I think you get the idea from there on . I'm sure if you search the internet you can find a good explanation of the general way of tackling this.

Yeah, and the reason he is taking two at a time with the continued fraction terms is because the simplest solution is for -1, not for 1.
Yeah, also there is a nice general formulae for it where you get (-1)n+1.

But anyway, the solution set nicely forms a group (or something like that, I missed most the lectures).
 
thanks to every one (especially Zurtex) for all your help. i think i understood now how to solve the equations. but additional information are always welcome. so feel free to fill me in.

thanks once again.
 

Zurtex

Science Advisor
Homework Helper
1,120
1
murshid_islam said:
thanks to every one (especially Zurtex) for all your help. i think i understood now how to solve the equations. but additional information are always welcome. so feel free to fill me in.

thanks once again.
Well here are the problems I got given earlier this year: http://www.ma.umist.ac.uk/nikita/117b/problems4.pdf

And here are the solutions: http://www.ma.umist.ac.uk/nikita/117b/solutions4.pdf

I'm not sure if you'll be able to make sense of the solutions, it depends how used to working out Continued Fraction Expansions from the square root of numbers. There is lots of material on the web if you're not used to it.
 
thanks Zurtex.
I haven't yet seen the pdf files. because right now i don't have an acrobat reader. i'll read those files as soon as i can get hold of a reader.

can you tell me how to solve the general equations of the form
x^2 - D*y^2 = c
if its not too much trouble.
 

Zurtex

Science Advisor
Homework Helper
1,120
1
murshid_islam said:
thanks Zurtex.
I haven't yet seen the pdf files. because right now i don't have an acrobat reader. i'll read those files as soon as i can get hold of a reader.

can you tell me how to solve the general equations of the form
x^2 - D*y^2 = c
if its not too much trouble.
Well it's not too easy to explain over the web. First of all you need to find the continued fraction of the square root of D, this can always be represented for the form:

[tex]\sqrt{D} = [a_0; \overline{a_1, a_2, \ldots, a_{n-1}, a_n}][/tex]

It happens to be that it's always true that an = 2a0. Now where c > 1. Look at some ak where 0 < k < n. If there is no ak = c, then there is no solution.

However, if you find some ak = c, then this splits in to two cases, either when k is even or odd. If k is even then a possible solution [itex]\alpha[/itex] for [itex]\alpha = x/y[/itex] is:

[tex]\alpha = [a_0; a_1, a_2, \ldots, a_{k-1}][/tex]

If k however is odd the solution is:

[tex]\alpha = [a_0; a_1, a_2, \ldots, a_{k-1}, a_k, a_1, a_2, \ldots, a_{k-1}][/tex]

For c < -1, it's the same set up (you look at when ak = |c|), but if I remember rightly you swap the solutions round for whether k is odd or even. When |c| = 1 then it's again the same but you also look at when k = n.

Sometimes there is not solution even when you get ak = |c|, you need to check it works.

Sorry for my very bad explanation, I actually only learnt this in to a crammed 2 hour session before I had a test on it, I didn't bother going to lectures. Oh well, I'll borrow some friends notes and make sure this is all correct, but I might not be able to get hold of them for over a week yet. But I know it's more or less correct, mess about with it for a bit if you want to see if you can get it to work.
 
thank you Zurtex for all your help. i think i can work it out from here. :smile:
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top