Karim Belabas on Fri, 21 Nov 2008 18:28:05 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Pell's equations and beyond


* Bill Allombert [2008-11-21 17:00]:
> On Wed, Nov 19, 2008 at 03:26:57PM -0800, Max Alekseyev wrote:
> > Dear pari-users,
> > 
> > I dream about having the functionality of Dario Alpern's quadratic
> > bivariate Diophantine equation solver:
> > http://www.alpertron.com.ar/QUAD.HTM
> > in PARI/GP. Is anything like that already present there?
> > At the moment, I'm not even sure if there is a simple way to solve
> > Pell's equations in PARI/GP.
> > 
> > Could you please clarify what is the best way (and if there exists one
> > without much programming) to solve the following equations in PARI/GP:
> > 
> > 3) Quadratic bivariate Diophantine equation in the general form: ax^2
> > + bxy + cy^2 + dx + ey + f = 0, where a,b,c,d,e,f are integer
> > coefficients ?
> 
> Well, as a starting point this hastily written script should work
> as long as b^2-4*a*c is not a square
> 
> An example:
> ? qesolve([1,3,7,2,5,-18])
> %28 = [[4, -2], [1, 1], [-6, 1], [0, -2]]
> 
> However if b^2-4*a*c, there is an infinite number of solution, and

... if b^2-4*a*c > 0, ...

> it only return the "smallest".

Bill treated the hardest case. Up to obvious changes of variables
(translations by rational vectors + clearing a common denominator), it
seems that the missing ones reduce to equations of the form

  Dx + Ey + F = 0            \\ a = b = c = 0

  Ax^2 + Ey + F = 0, A != 0  \\ else b^2 - 4ac = 0

  Bxy + F = 0, B != 0        \\ else b^2 - 4ac a square

The first one is essentially 'bezout', the last one 'divisors', and both
are trivial to program. The second one involves all square roots mod E
of -F/A (for each x congruent to one such root, you get a unique y), and
is slightly more painful. About five lines, say, using factor +
sqrt(p-adic numbers) + forvec + chinese.

So, exercise: complete Bill's program to really treat *all* cases.
(Specifying properly how you describe the set all solutions, when there
are infinitely many.) This should double its size at most, and I don't
think this qualifies as "too much programming".

Then make the script available to all of us :-).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`