Re: Pell's equations and beyond

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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
it only return the "smallest".

Cheers,
Bill.

qeeval(Q,x,y)=local(a=Q[1],b=Q[2],c=Q[3],d=Q[4],e=Q[5],f=Q[6]);a*x^2+b*x*y+c*y^2+d*x+e*y+f

qered(Q)=
{
  local(a=Q[1],b=Q[2],c=Q[3],d=Q[4],e=Q[5],f=Q[6],F,u,v);
  F=[2*a,b;b,2*c]^-1*[-d,-e]~;u=F[1];v=F[2];
  D=denominator(content(F));
  [a,b,c,D^2*(u^2*a+v*u*b+v^2*c+u*d+v*e+f),D,D*u,D*v]
}

qesolve(Q)=
{
  local(a,b,c,f,V,B,L,u,v,w,S=List());
  if (issquare(Q[2]^2-4*Q[1]*Q[3]),error("reducible equation"));
  Q=qered(Q);a=Q[1];b=Q[2];c=Q[3];f=Q[4];D=Q[5];
  B=bnfinit(x^2-b*x+a*c);
  L=bnfisintnorm(B,-f*a);
  for(i=1,#L,
    for(j=1,B.tu[1],w=lift(L[i]*B.tu[2]^(j-1));
    u=polcoeff(w,0);v=polcoeff(w,1);
    if (denominator(u)!=1 || denominator(v)!=1,next);
    if (u%a!=0,next,u\=a);
    if ((u-Q[6])%D!=0,next,u=(Q[6]-u)\D);
    if ((v-Q[7])%D!=0,next,v=(Q[7]-v)\D);
    listput(S,[u,v]);
  ));Vec(S)
}