From: Robin Chapman Subject: Re: Solving Pellians Date: Thu, 02 Dec 1999 13:56:04 GMT Newsgroups: sci.math Keywords: when are Pellian (norm) equations solvable? In article <825qke$5t0$1@nnrp1.deja.com>, Bob Silverman wrote: > In article <824dqk$klu$1@morgoth.sfu.ca>, > erick@sfu.ca (Erick Bryce Wong) wrote: > > Are there any known sufficient conditions on k,d for a Pellian equation > > x^2 - dy^2 = k to have a solution > > Hint: Reduce the equation mod d, then think "Quadratic > Reciprocity". > > Another way of looking at it: x^2 - k must be reducible mod d. > > Another way: k must split in Q(sqrt(d)). These will give necessary rather than sufficient conditions. Sufficient conditions will be harder to give, since the non-vanishing of the classgroup will give obstructions to such local conditions implying solubility. What these local conditions ensure is that there is a quadratic form of the same discriminant as x^2 - dy^2 representing k. Once this is found, then solubility amounts to checking these 2 quadratic forms are equivalent, which can be checked by computing their cycles of reduced forms. I don't have my copy to hand, but surely this must be covered in Henri Cohen's book on computational number theory? -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "`Well, I'd already done a PhD in X-Files Theory at UCLA, ...'" Greg Egan, _Teranesia_ Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Kurt Foster Subject: Re: Solving Pellians Date: Thu, 02 Dec 1999 17:00:26 GMT Newsgroups: sci.math In <824dqk$klu$1@morgoth.sfu.ca>, Erick Bryce Wong said: . Are there any known sufficient conditions on k,d for a Pellian equation . x^2 - dy^2 = k to have a solution (besides the obvious "k is a perfect . square" :)? Or perhaps an effective algorithm for deciding whether it . has one? I'm primarily dealing with values of k larger than those which . might come up in the continued fraction convergents. Plenty of necessary conditions. For each prime factor q of d we have x^2 == k (mod q); thus, if NOT(q|k), then k must be a quadratic residue (mod q). Similarly, if p is a prime factor of k dividing k an odd number of times, and NOT(p|d), then d must be a quadratic residue (mod p) [there may some other details to consider here, but I'm too lazy to consider them]. So in some cases, the existence of solutions can be ruled out. Sometimes, these necessary conditions are also enough to establish the existence of solutions, e.g. if the ring of integers of Q(sqrt(d)) is a principal ideal domain. For example, if a prime p == 1 or 7 (mod 8), then x^2 - 2*y^2 = p is guaranteed to be solvable. But not every such ring is a PID; and when it isn't, the necessary conditions aren't enough. There are additional theoretical tools that can be brought to bear in such a case; the basic problem is to decide whether, kZ being the norm of an ideal, is the norm of a *principal* ideal. But, even when solutions are known to exist (as in the preceding paragraph), there remains the problem of finding them. There are methods of finding all solutions to such an equation. One method, described in Chrystal's "TEXTBOOK OF ALGEBRA", involves successively transforming the equation, at each step replacing k with a number k', |k'| < |k/2|, until you reach a value so small that it would have to show up in the continued-fraction development of sqrt(d). If any solutions to the final "reduced" equation are found, then you have to backtrack, at each step finding all possible solutions, till you at last get back to your original equation. It's tedious, but it works. ============================================================================== From: jpr2718@aol.com Subject: Re: Solving Pellians Date: Fri, 03 Dec 1999 00:49:14 GMT Newsgroups: sci.math To: erick@sfu.ca In article <824dqk$klu$1@morgoth.sfu.ca>, erick@sfu.ca (Erick Bryce Wong) wrote: > Are there any known sufficient conditions on k,d for a Pellian equation > x^2 - dy^2 = k to have a solution (besides the obvious "k is a perfect > square" :)? Or perhaps an effective algorithm for deciding whether it > has one? I'm primarily dealing with values of k larger than those which > might come up in the continued fraction convergents. > > -- Erick > Some references for methods to solve particular equations, as best I can remember are: Dario Alpern's web page: go to http://members.tripod.com/% 7Ealpertron/ENGLISH.HTM, click on Quadratic two integer variables equation solver, and click on Methods. H. Edwards, Fermat's Last Theorem, Springer - see material on cyclic method, spread over several chapters IIRC, especially towards end. One exercise towards the end of the book is to write a computer program to solve equations of the form ax^2 + bxy + cy^2 + dx + ey + f = 0. Find that exercise, and work backwards through the book from there. G. Chrystal, Algebra (or A Textbook of Algebra, or ??), Dover (?1950's reprint of 1930's textbook), 2 volumes - gives a method (may have been reprinted more recently by Chelsea) Jean Dieudonne, Mathematics-The Music of Reason, Springer-Verlag, 1992 - gives ?Lagrange's method Some authors give a range to use to search for basic solutions, from which all others can be derived. Some texts give incorrect ranges, so be careful. Mollin, Fundamental Number Theory with Applications, CRC Press, gives correct ranges. Incorrect ranges are given in LeVeque, Topics in Number Theory, Vol. 2 (I think), and Rose, A Course in Number Theory. I can e-mail an Excel workbook that solves these equations when d and k are small, and so is the smallest solution to x^2 - dy^2 = 1. John Robertson Sent via Deja.com http://www.deja.com/ Before you buy.