# How to find all solutions of Pell equation

1. Jun 12, 2005

### 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?

Last edited: Jun 13, 2005
2. Jun 13, 2005

### Zurtex

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?

3. Jun 13, 2005

### 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) (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.

Last edited: Jun 13, 2005
4. Jun 13, 2005

### murshid_islam

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?

5. Jun 14, 2005

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

6. Jun 14, 2005

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

7. Jun 14, 2005

### murshid_islam

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.

8. Jun 15, 2005

### Zurtex

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

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

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

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

9. Jun 15, 2005

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

10. Jun 15, 2005

### Zurtex

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

11. Jun 15, 2005

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

12. Jun 16, 2005

### Zurtex

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.

13. Jun 17, 2005

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

14. Jun 17, 2005

### Zurtex

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

15. Jun 19, 2005

### murshid_islam

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