Date: Tue, 23 Feb 1999 14:48:40 -0300 From: Dario Alejandro Alpern To: Dave Rusin Subject: Re: Linear recurrence among solutions of quadratic diophantine equation Dave Rusin wrote: > >The only gap that > remains here is to find all the starting values that, if we apply the formula I > gave you in the previous e-mail, we finally find all solutions to Ax^2 + Bxy + > Cy^2 + Dx + Ey + F = 0. Is this set of starting values finite? If so, how can I > compute them? > > I guess my own preference would not be computationally rapid, but it would > work. With some changes of variable you transform this to a Pell's equation > X^2 - D Y^2 = N. This then asks for a ring element X + zeta Y (zeta^2=D) > whose norm is N (here's where I'm slipping into algebraic number theory). > It's easier to ask for the _ideals_ of the ring whose norm is N; all you > have to do is (1) factor N in the usual ring of integers (2) find out how > the prime factors factor in the extension ring (3) list all ways of > choosing from among the prime ideals found so as to get a norm equal to N. > This gives a complete, finite collection of ideals with the right norm. > You then have to decide which are principal ideals and discard the rest. > Taking a generator of each of the remaining ideals gives a complete, finite > collection of ring elements X + zeta Y whose norm is N -- complete in > the sense that any other such element is (one of these) times (some unit > in the ring). Except for just a few values of D, the units in the ring > consist of the powers of one "fundamental" unit, more or less corresponding > the the "r, s" in your recursion for generating more solutions. > > One final complication is that the changes of variables I began with > might require that X and Y satisfy some congruence conditions. This > can be handled by splitting each of the cases at the end of the previous > paragraph into several subcases, discarding the ones which lead to fractional > solutions. You would need to replace the fundamental unit by the smallest > power of that unit which preserves the congruence conditions you seek. > > There are several references to this material on > index/11DXX.html > which you may have already seen. (scan for "Pell" and for "quadratic"). > Many people refer to Chrystal's old algebra book for details but I must > confess I haven't seen it. I believe he uses Gauss's original reduction > procedure which is more or less the continued-fraction method but can be > interpreted as "trying to divide by the fundamental unit until reaching > one of a finite number of minimal solutions". > > Good luck. > dave Yes, I read all your material about this topic. I actually can find the solutions of the equations of the form Ax^2 + Bxy + Cy^2 + F = 0 (1). Is there any way to change variables to transform the complete equation to the equation (1)? The problem with the reduction to a Pellian equation is that it produces too many solutions that should be discarded since they do not hold the congruences you mention above. Possibly if I transform to (1) the number of solutions to discard is reduced considerably. Best regards, -- Dario Alejandro Alpern Buenos Aires - Argentina http://members.tripod.com/~alpertron (en castellano) http://members.tripod.com/~alpertron/ENGLISH.HTM (English) Si su navegador no soporta JavaScript: http://members.tripod.com/~alpertron/INDEX2.HTM If your browser does not support JavaScript: http://members.tripod.com/~alpertron/ENGLISH2.HTM Antes era fanfarron... Ahora soy perfecto!! ============================================================================== Date: Tue, 23 Feb 1999 16:13:31 -0300 From: Dario Alejandro Alpern To: Dave Rusin Subject: Re: Linear recurrence among solutions of quadratic diophantine equation Dave Rusin wrote: > >I actually can find the solutions of the equations of the form Ax^2 + > >Bxy + Cy^2 + F = 0 (1). Is there any way to change variables to > >transform the complete equation to the equation (1)? > > You're just changing the function to have its critical point at the > origin, right? So you need a substitution x=x'+x0, y=y'+y0, where (x0,y0) > is the critical point of the original quadratic, that is, the > solution to the equations df/dx=df/dy=0. These are the solution to > 2A x + B y + D = 0 > B x + 2C y + E = 0 > This introduces B^2-4AC in the denominators, so as you may suspect, you > must clear denominators, solve an integral problem, and then at the end > discard solutions which do not have x,y in the appropriate congruence > classes modulo B^2-4AC. I really don't think there's any way to do it > which does not involve solving a problem which introduces these extra > solutions which have to be rejected at the end. > > dave Dave, Thanks for your answers. I will check both methods to determine which one produce less extra solutions (so it is faster in Javascript, a slow interpreted language, but useful for creating calculators on Internet). By the way, did you use my Diophantine Quadratic Equation Solver at the address I gave you in the previous post? If you do, please run it in "step-by-step" mode. I will appreciate your comments. Thanks a lot. The addresses are: http://members.tripod.com/~alpertron/QUAD.HTM (Javascript) http://members.tripod.com/~alpertron/JQUAD.HTM (Java) Best regards, [sig deleted -- djr