From: jpr2718@aol.com (Jpr2718) Newsgroups: sci.math Subject: Re: General Pell equation: x^2 - N*y^2 = D Date: 03 Jun 1998 01:13:32 GMT >I'm looking for a process to solve the general Pell equation--even knowing if >such a process exists would be helpful to me. A reference to a helpful number >theory book would be most welcome! > > There are a number of processes for solving these equations. The continued fraction method solves the equation x^2-dy^2=m for d>0 and m=1 or -1 as explained in Olds, Continued Fractions, published in the New Mathematical Library by the Mathematical Association of America, or Niven, Zuckerman and Montgomery, Intro to Number Theory, 5th edition, or many other elementary number theory books. The continued fraction method is also the method of choice if d>0 is not a square and abs(m)0, essentially abs(m)>sqrt(d), either use a brute force search up to limits given here and there, or use either the cyclic method or the method given in Chrystal's Algebra. The limits for a brute force search are given correctly in Richard Mollin's Fundamental Number Theory with Applications and I think also in his book Quadratics. They are given incorrectly in Rose's A Course in Number Theory (1st or 2nd editions) and in Leveque, Topics in Number Theory, vol 1 (I think, it might be vol. 2). The incorrect limits are not too hard to fix. Add zero as a lower bound for the search, and increase the upper bound on one of these a bit as I recall. Essentially solutions fall into families. If you have one solution, and generate another from the solution to x^2-dy^2=1, then all other families (if any) have a solution that lies between these two. So you just need to search between two such. If there are no solutions, you'll need to check a reference to be able to tell when you've searched far enough. The cyclic method is explained in Edward's Fermat's Last Theorem. Chrystal's Textbook of Algebra (published in the 1930's?, more recent Dover reprint, but probably out-of-print by now) gives a recursive method. Of course Gauss's Disquisitions Arithmeticae covers methods for solving these equations, but is a slow read. If you have Excel 6.0 or later for a PC with Windows, I can e-mail you an Excel file that uses the continued fraction method for the d>0, m=+/-1, +/-4 equations, and uses a search method for all others with d>0, not square. If you have Word 6.0 or later for a PC with Windows, I can e-mail you a file that gives thealgorithm (no proofs) for the continued fraction method for the +/-1 and +/-4 equations. For d<0 the most practical method is a brute force search. The limits of the search are easy to work out. For large coefficients, methods in Cox's Primes of the Form x^2+ny^2 might be useful. jpr2718@aol.com (no spell checker on Aol yet - sorry) ============================================================================== From: Richard Pinch Newsgroups: sci.math.research Subject: Re: general Pell equation: x^2 - N*y^2 = D Date: Thu, 04 Jun 1998 16:02:03 +0100 rhiebert@my-dejanews.com wrote: > > I would like to know if there is a process for solving the general Pell > equation: > > x^2 - N*y^2 = D > > I know how to do this if D=1 (with the convergents of the continued fraction > form of sqrt(N)) but I'm going nowhere fast with the general form. There is a very useful discussion in chapter 7.4 of Edwards "Fermat's Last Theorem", Springer GTM 50. The "cyclic method" generalises the CF method for the case D=1. -- Richard Pinch Queens' College, Cambridge rgep@cam.ac.uk http://www.dpmms.cam.ac.uk/~rgep ============================================================================== From: jpr2718@aol.com (Jpr2718) Newsgroups: sci.math Subject: Re: Procedure to solve General Pellian Equations Date: 24 Jul 1998 01:57:34 GMT >I was "playing" with the coefficients of the Pellian equations and I >found a method to solve them. > > Professor Alpern, In general, it appears that your method would miss solutions. For example, x^2-2y^2=2 has solutions, (2,1), (10,7), ... Your method suggests looking at x^2-8y^2=2, which does not have any solutions. A counterexample closer to your example is x^2-7y^2=29, which has solutions, while x^2-847y^2=29 has no solutions. There are several methods for solving the Pellian equation when |N|>sqrt(d). One is to use a brute-force search. If N<0 then search on y=sqrt(abs(n/d)) to sqrt((abs(n)(x1+1))/(2d)) and if N>0 search on y=0 to sqrt((n(x1-1))/(2d)) where (x1, y1) is the minimum positive solution (x, y) to x^2-dy^2=1. If N<0, for each positive (x, y) found by the search, also take (-x, y). If N>0, also take (x, -y). In either case, all positive solutions are generated from these using (x1, y1) in the standard way. See Mollin, Fundamental Number Theory with Applications, pages 299 and 300 for equivalent formulas. Note that the formulas in LeVeque and Rose are not quite right. Another method is the cyclic method, explained in Chapter 7 of Edward's Fermat's Last Theorem. Chrystal, Textbook of Algebra, Part 2, pp 482ff, describes Lagrange's reduction of the case |N|>sqrt(d) to some number of cases with |N| Newsgroups: sci.math Subject: Re: Procedure to solve General Pellian Equations Date: 24 Jul 1998 14:16:25 GMT In <35B886C3.EF40BD0B@hotmail.com>, Dario Alejandro Alpern said: [snip] . Jpr2718 wrote: .. Chrystal, Textbook of Algebra, Part 2, pp 482ff, describes Lagrange's .. reduction of the case |N|>sqrt(d) to some number of cases with .. |N| Jpr2718 wrote: > > > >I was "playing" with the coefficients of the Pellian equations and I > > >found a method to solve them. > > > > > Professor Alpern, > > > > In general, it appears that your method would miss solutions. For example, > > > x^2-2y^2=2 has solutions, (2,1), (10,7), ... Your method suggests looking > at > > x^2-8y^2=2, which does not have any solutions. A counterexample closer to > your > > example is x^2-7y^2=29, which has solutions, while x^2-847y^2=29 has no > > solutions. > > > > John, > > Yes, you are right. I think that there should be a better method to find the > prime > number that squared multiplies D. Maybe using simple modular considerations > we can > avoid those counterexamples. More complicated counterexamples are possible. For instance, for x^2-5y^2=4, the equation x^2-20y^2=4 generates some but not all solutions of the original equation. I doubt that for all equations x^2-dy^2=m, |M|>sqrt(d) there always is a prime p so that solutions to x^2-(dp^2)y^2=m generate all solutions to x^2-dy^2=m. In general, I would expect several primes to be necessary, and that it would be difficult to tell when one had found all solutions. > > > There are several methods for solving the Pellian equation when |N|>sqrt(d) > . > > One is to use a brute-force search. If N<0 then search on y=sqrt(abs(n/d)) > to > > sqrt((abs(n)(x1+1))/(2d)) and if N>0 search on y=0 to sqrt((n(x1-1))/(2d)) > > where (x1, y1) is the minimum positive solution (x, y) to x^2-dy^2=1. If > N<0, > > for each positive (x, y) found by the search, also take (-x, y). If N>0, > also > > take (x, -y). In either case, all positive solutions are generated from > these > > using (x1, y1) in the standard way. See Mollin, Fundamental Number Theory > with > > Applications, pages 299 and 300 for equivalent formulas. Note that the > > formulas in LeVeque and Rose are not quite right. > > > > In this case the number of computations is very high. Consider, for example > the > equation x^2 - 991 y^2 = 1. In this case x1 is a 36-digit number and y1 is > a > 35-digit number. Then it would be impossible to perform the brute-search > method in > this way. With a well-chosen multiplier as I wrote above it could be > possible to > find solutions in a reasonable amount of time. I agree brute force search will not work in cases where coefficients or solutions to the equation x^2-dy^2=1 are large. On the other hand, what guarantee is there that the smallest primeneeded to find a family of solutions isn't almost as large as the smallest solution to x^2-dy^2=1? Minor quibble: I get 30 digits and 29 digits as the lengths of the x and y that are the smallest positive solutions to x^2-991y^2=1. x=379 516 400 906 811 930 638 014 896 080, y= 12 055 735 790 331 359 447 442 538 767. > > > Another method is the cyclic method, explained in Chapter 7 of Edward's > > Fermat's Last Theorem. Chrystal, Textbook of Algebra, Part 2, pp 482ff, > > describes Lagrange's reduction of the case |N|>sqrt(d) to some number of > cases > > with |N| > > > I donīt know this method. Can you explain it? Both of these methods are somewhat complicated, and it's best if you read these sources. I would expect both are easily available. Chrystal was THE college algebra book in the 1930's I think. It might be in storage, but any college math library should have it. Also, it's a Dover paperback, but I don't know whether it's still in print. Edwards' discussion of the cyclic method is more like 50 pages, so it's best if you find the book. Cohen's A Course in Computational Algebraic Number Theory might also be useful for implementing either of these methods. > > > John Robertson > > jpr2718@aol.com > > Best regards, > -- > Dario Alejandro Alpern > ============================================================================== From: r3769@aol.com (R3769) Newsgroups: sci.math Subject: Re: Procedure to solve General Pellian Equations Date: 25 Jul 1998 03:44:12 GMT > There's an older hardcover edition >published by Chelsea, but that may be out of print. >< Nope. Try amazon.com. R. ============================================================================== From: Helmut.Richter@lrz-muenchen.de (Helmut Richter) Newsgroups: sci.math Subject: Re: Solving general two integer variables quadratic equation calculator Date: 30 Dec 1997 20:19:33 GMT Dario Alejandro Alpern writes: >All trivial cases are handled. I have trouble solving the general >Pellian equation >x^2 - P y^2 = N You might try to find the somewhat old-fashioned (around 1900) Algebra textbook by Crystal. It discusses such equations in detail. Helmut Richter