From: rgep@emu.pmms.cam.ac.uk (Richard Pinch) Newsgroups: sci.math Subject: Re: Using Pell's Equation to find integer solutions Date: 18 Mar 1996 10:02:52 GMT In article <3c7cc$81b19.23e@www.qed.com> rdsilverman@qed.com writes: >In article <4i25th$27a@news2.deltanet.com>, writes: >> I am trying to determine if there exist integer solutions >> x,y for a equations of the form Ax^2 + Bx + C = y^2 >> where A,B, and C are integers. >> A number of kind folks have referred me to Pell's equation, but >> I have been having trouble transforming my equation to the >> requisite x^2-Dy^2 = 1. I can get to x^2-Dy^2 = N. >That is all you need. If N is a quadratic residue (of D) then a solution >exists. Otherwise no. The way you find solutions is to find out how N >factors in Q(sqrt(D)). Then to get subsequent solutions, you just multiply >the first one by powers of the fundamental unit of the field. Unfortunately it's not that simple. There are three obstructions to the recipe. Firstly, every prime factor of N has to split in the field Q(sqrt(D)), or occur to an even power (when it just divides the values x and y). Secondly, even if it splits, the power to which it occurs in N has to be a multiple of its order in the ideal class group. Thirdly, the sign on N has to be right, or there has to be a unit of odd norm, i.e. a solution of Pell with RHS equal to -1. Richard Pinch; Queens' College, CambridgE ============================================================================== Date: Mon, 18 Nov 96 08:39:41 CST From: rusin (Dave Rusin) To: randall_rathbun@rc.trw.com Subject: Re: Fermat (Pellian) Equation >Can you point me to people who know how to find the fundamental >solutions and/or classes to the generalized Fermat (Pell) equation >x^2-Dy^2 = N where D is square free, but N may or maynot be. I'm >having trouble finding material on this, after searching at the >Science/Technical Library at UCSD which is rather voluminous. All >I have found is some T. Nagell's information, and a section in >Don Redmond's Introduction to Number Theory. He just bounds solutions >but does NOT show how to actually find them individually. I'd >appreciate finding someone who knows how to locate such solutions, >factoring over rings, I believe. Pardon my ignorance. Thanks for >your help. There are several different hurdles into which you may run, depending on what exactly you want to do. For example, if you could find a way of computing the first nontrivial solution to x^2-Dy^2=1 which took, oh, about log(D) operations, then you would have found the Holy Grail of factorization: if D = pq is a product of two primes, for example, that smallest solution would have x=+1 mod p and x=-1 mod q (or vice versa) so that gcd( D, x-1 ) or gcd( D, x+1 ) would be a nontrivial factor of D. So if you wanted to solve the equations integrally you either have to accept something slow (e.g. a case-by-case check up to the upper bounds you mentioned) or you have to assume some other information (e.g. the prime factors of D). If you do have the factorization of D I guess you can solve the equation first mod-p, then p-adically, then rationally, then integrally. The first step is possible (and efficient) iff N is a square mod p, the second is automatic for any p>2 (you don't really need to worry about p=2 if D>0 since the equation is solvable over the reals in that case), the third step also automatic (that's the Hasse-Minkowski theorem: for quadratic equations, "solvable globally" is the same as "solvable everywhere locally"). Surely there is a text containing just the material you want to solve this problem but I don't know a reference; however, I looked in my copy of Borevich and Shafarevich's Number Theory and found that Chapter 2 contains fairly explicit discussions of how to solve the general problem f(x,y)=N with f a quadratic. (For example the exercises assume the reader can find all solutions of x^2-80y^2=-16 ). I suppose you know that there are a number of obstructions to your ability to solve the equation at all. I have enclosed a recent post to sci.math which addresses the issues. Finally I assume you know about using the continued fraction algorithm to generate solutions to your equation. There is a range of values (I think it's " N < sqrt(D) " ) within which all solutions of the Pell equation must be among the numbers (x_n/y_n) generated by the continued-fraction algorithm for sqrt(D). Incidentally if you just want to do the computations you could get one of the computer-algebra packages to work for you. I see that KASH, for example, has routines to find all solutions to equations of the form Norm(x)= N in a number field. dave [Pinch's post, above, attached and sent -- djr] ============================================================================== See also 95/quadratics