How to find all solutions of Pell equation

[murshid_islam]

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?

 

[Zurtex]

I would just use a continued fraction expansion on the square root of P where the equation is: x² - Py² = a

What exactly do you know to do so far?

 

[robert Ihnot]

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: $$(1-\sqrt2)<br /> (1+\sqrt2)=-1$$ 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:

$$(1-\sqrt{2})(X-\sqrt{2}Y)= (X+2Y)-\sqrt2(X+Y)$$

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

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.

 

[murshid_islam]

I would just use a continued fraction expansion on the square root of P where the equation is: x² - Py² = a

What exactly do you know to do so far?

the equation i want to solve is of the form:
x² - Py² = 1

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

 

[shmoe]

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

 

[Zurtex]

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.

 

[murshid_islam]

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]

Well all where D is a non square number it always true that:

$$\begin{multline*} <br /> \sqrt{D} = \\ <br /> 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) <br /> \end{multline*}$$

This is more simply expressed as:

$$\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}]$$

Now, if you don't mind, I'd rather not explain in general how to solve the equation x² - Dy² = c, as the methods split into 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:

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

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

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

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

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

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

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

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

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. 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.

 

[robert Ihnot]

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]

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)ⁿ⁺¹.

But anyway, the solution set nicely forms a group (or something like that, I missed most the lectures).

 

[murshid_islam]

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]

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.

 

[murshid_islam]

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]

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:

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

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

However, if you find some a_k = c, then this splits into two cases, either when k is even or odd. If k is even then a possible solution $\alpha$ for $\alpha = x/y$ is:

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

If k however is odd the solution is:

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

For c < -1, it's the same set up (you look at when a_k = |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 a_k = |c|, you need to check it works.

Sorry for my very bad explanation, I actually only learned this into 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.

 

[murshid_islam]

thank you Zurtex for all your help. i think i can work it out from here.