Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

How to find all solutions of Pell equation

  1. Jun 12, 2005 #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: Jun 13, 2005
  2. jcsd
  3. Jun 13, 2005 #2

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. Jun 13, 2005 #3
    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: Jun 13, 2005
  5. Jun 13, 2005 #4

    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?
     
  6. Jun 14, 2005 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Jun 14, 2005 #6

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Jun 14, 2005 #7
    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.
     
  9. Jun 15, 2005 #8

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Jun 15, 2005 #9
    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.
     
  11. Jun 15, 2005 #10

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  12. Jun 15, 2005 #11
    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.
     
  13. Jun 16, 2005 #12

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Jun 17, 2005 #13
    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.
     
  15. Jun 17, 2005 #14

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  16. Jun 19, 2005 #15
    thank you Zurtex for all your help. i think i can work it out from here. :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: How to find all solutions of Pell equation
  1. Pell's Equation (Replies: 4)

Loading...