From: John Robertson Subject: Re: Generalized Pell equation Date: Sun, 17 Sep 2000 14:58:45 GMT Newsgroups: sci.math Summary: [missing] In article , malai@winner.fr (Gianfranco Oldani) wrote: > Hi, > I have reduced one of my problem to look at integral (x1,y1) > solutions to the generalized pell equation : > > X^2 -D*Y^2 = K > where D > 0 and K < 0. > > Is it possible or what are the conditions on D and K > for which it is ? > Some of these equations have solutions, and some do not. Criteria for K have been developed for a few D, but there is no general criterion that works for all D and K. If D is a square, Say D = d^2, then factor the LHS as (X-dY)(X+dY)=K. Find all ways to factor K=MN, and then see if the pair of linear equations X-dY=M, X+dY=N has an integral solution. If D is not a square, there are five good methods for solving any given equation X^2 -D*Y^2 = K: brute force search (good only if K is "small" and the solutions to X^2 - D*Y^2 = 1 are "small"), Lagrange's system of reduction, the cyclic method, use of the theory of binary quadratic forms, and the Lagrange/Matthews method. A post by me (and posts by others) at the number theory listserver, http://listserv.nodak.edu/archives/nmbrthry.html, dated May 16, 2000, discusses some of these methods, and gives some references. There are some additions I would make to that post. One is that the web page by Dario Alperon at http://members.tripod.com/%7Ealpertron/ENGLISH.HTM does not always find all solutions to such equations, although it usually works fine. Another is that a good reference on using binary quadratic forms to solve these equations is Adolf Hurwitz and Nikolaos Kritikos, Lectures on Number Theory, Springer-Verlag, New York, 1986. Presented by Adolf Hurwitz, edited for publication by Nikolaos Kritikos, translated, with some additional material, by William C. Schulz. Especially Chapter 6, sections 46 to 67, pp. 157-264. Finally, and most significantly, I think that the best way to solve these is the method designated Lagrange/Matthews above. Keith Matthews has recently discovered in Lagrange's Oeuvres a method that is a generalization of the standard continued fraction method for solving the equation when K = +/-1. He has a pre-print available at his web site http://www.maths.uq.edu.au/~krm/. Go to "publications." At the very end is a section on pre-prints. Look for the paper "Patz." (The site seems to be down at the moment, so I am working form memory here, always dangerous for me.) In any event, the title is "The Diophantine equation x^2 - Dy^2 = N, D>0", and the first sentence of the abstract is, "We describe a simple continued fraction based method due to Lagrange, ..." To summarize this method, to solve x^2 - dy^2 = N (changing notation on you), do the following. For each f>0 so that f^2 divides N, set m = N/f^2, set Q_0 = abs(m) and do the following. For each P_0, -Q_0/2 <= P_0 <= Q_0/2, with P_0^2 - d == 0 (mod Q_0), apply the "PQa" method starting with P_0 and Q_0. When Q_i = 1, read a solution to the equation x^2-dy^2=+/-m as x=Q_0*A_{i-1} - P_0*B_{i-1}, y=B_{i-1}, and multiply by f to get a solution to x^2-dy^2=+/-N. That's it. If you grab one solution for each P_0, you will have a solution in every class. By the "PQa" method, I mean the standard method of computing the continued fraction expansion of a quadratic irrational by computing a_i=int(P_i+sqrt(d))/Q_i, P_{i+1}=a_i*Q_i - P_i, Q_{i+1}=(d-P_{i+1} ^2)/Q_i. A_i/B_i is a convergent. These are computed by taking A_-2 = 0, A_-1=1, B_-2=1, B_-1=0, and then A_i = a_i*A_{i-1} + A_{i-2}, B_i = a_i*B_{i-1} + B_{i-2}. Some of these recursions start with i=0, and some with i=1, which I leave to you to sort out. See Henri Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993, Section 1.5, Computing Square Roots Modulo p, pp. 31-36, for methods to solve P_0^2 - d == 0 (mod Q_0). John Robertson Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: John Robertson Subject: Re: Generalized Pell equation Date: Mon, 18 Sep 2000 17:51:39 GMT Newsgroups: sci.math To: malai@winner.fr (Gianfranco Oldani) Here are better directions to Keith Matthews pre-print: Go to http://www.maths.uq.edu.au/~krm/. Click on "Publications." Go to the bottom and look for: Unpublished notes, in the pipeline, and get "The diophantine equation x2-Dy2=N, D > 1, in integers" (pdf 144K), (to appear in Expositiones Mathematicae) Also, I misspelled Dario Alpern's name. Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: John Robertson Subject: Solving Pell Equations Date: Sun, 10 Dec 2000 02:24:41 GMT Newsgroups: sci.math In response to the occasional question about solving Pell equations, I have posted descriptions of algorithms to solve any of these equations x^2 - dy^2 = N for d a positive integer, not a square, and N a nonzero integer. For the algorithms presented, the web page does not provide proofs that the algorithms work as claimed, but the references cited provide the proofs. The web page provides a summary of a method developed recently by Keith Matthews to solve the general Pell equation. I think this method has a lot of advantages over the methods that were previously well known (Lagrange's system of reductions, use of binary quadratic forms, the cyclic method). Also included is an algorithm for solving the equation x^2 - dy^2 = +/- 4, and a discussion of its relation to the equation x^2 - dy^2 = +/-1. The write-up is available at http://hometown.aol.com/jpr2718/pelleqns.html. Please direct comments to me at JPR2718@AOL.COM. John Robertson Sent via Deja.com http://www.deja.com/ Before you buy.