Given $a,b\in\Bbb Q_+$, is there an easy way to decide if $$S_{a,b}=\{(x,y)\in\Bbb Z^2:ax^2 + by^2=1\}=\emptyset?$$
I am more interested in seeing if there is a quick way to test for case when solutions do not exist.
Given $a,b\in\Bbb Q_+$, is there an easy way to decide if $$S_{a,b}=\{(x,y)\in\Bbb Z^2:ax^2 + by^2=1\}=\emptyset?$$
I am more interested in seeing if there is a quick way to test for case when solutions do not exist.
It's better to write it as $ax^2+by^2=c$ with $a,b,c\in\mathbb{Z}$. Your assumption that $a$ and $b$ are positive implies that there is a real solution. So now you can use Legendre's theorem (criterion), which says that $ax^2+by^2+cz^2=0$ (with $a,b,c$ nonzero integers, squarefree, pairwise relatively prime, and not all positive or negative) has a non-trivial solution in integers if and only if $$ \left({-ab\atop c}\right)=1 \quad\hbox{and}\quad \left({-ac\atop b}\right)=1 \quad\hbox{and}\quad \left({-bc\atop a}\right)=1. $$ So it just comes down to checking these three quadratic residue symbols. What's really going on is that a quadratic polynomial equation has a solution in integers if and only if it has a real solution and a $p$-adic solution for all $p$.
For a proof of Legendre's theorem, see for example A Classical Introduction to Modern Number Theory, Ireland and Rosen, Chapter 17, Section 3.
I think it is best to write the equation $ax^2+by^2=c$ with $a,b,c$ positive integers with $gcd(a,b,c)=1$.
Let me first give you a slow algorithm: since $a,b$ are positive a solution must satisfy $x^2\le c/a$ and $y^2\le c/b$, so you can enumerate these possible $x$ and $y$ and see whether you find a solution. Slightly better, only enumerate the $y$'s (or $x$'s) and check whether $c-by^2$ is divisible by $a$ and the quotient is a square.
Now here is what you can do in the special case $a=1$: $x^2+by^2$ is the norm form of the imaginary quadratic order $\mathbb{Z}[\sqrt{-b}]$. After factoring $c$, you can write down the list of ideals of norm $c$. Solvability of the equation is then equivalent to the principality of one of these ideals. This can be tested by computing the shortest vectors of the ideal for the norm quadratic form, which you can do in polynomial time. I suspect that there is a similar algorithm in the general case $a\neq 1$ but I have not worked it out.
Edit: Your second equation $ax^2+by=c$ ($a,b,c$ integers) is simpler. If $x$ is given, there is a solution $y$ if and only if $ax^2=c \pmod{b}$. So you should factor $b$, then test whether $ca^{-1}$ is a square modulo $b$ and find all the possible square roots, and finally all the solutions are given by taking all lifts of those roots and the corresponding $y$.
I thinks pari/gp can solve this via bnfisintnorm
.
For integers, $a,b,c$, you are solving $ax^2+by^2=c$ with $ab$>0.
Solving symbolically:
$$ x= \pm {\frac {\sqrt {-a \left( b{y}^{2}-c \right) }}{a}} $$.
The denominator is integer, so the numerator must be integer divisble by $a$.
Squaring the numerator we get:
$$ X^2+aby^2=ac \qquad(1) $$
Since $ab>0$, (1) has finitely many solutions and it is Pell-like since it is monic in $X$.
There are no units in the the number field with defining polynomial
$X^2+ab$, so pari's bnfisintnorm(K,ac)
will give solutions and you
must find those $X$ divisible by $a$.
Prototype pari implementation
{
solveabc(a,b,c)=
/*
pari/gp implementation for solving
ax^2+by^2=c
https://mathoverflow.net/questions/202037/deciding-a-quadratic-diophantine-equation
sample usage:
? \r solveabc.gp
? a=7;b=5;T=solveabc(a,b,a*2^2+b*3^2)
%64 = [[2, 3], [2, -3]]
*/
if(!issquarefree(a*b),print("ab is not squarefree, likely will fail"););
K=bnfinit('x^2+a*b,1);
no=bnfisintnorm(K,a*c);
if(no==[],print(" a is not norm, no solutions");return([]));
r=[];
for(i=1,#no,
v=lift(no[i]);
X=polcoeff(v,0)/a;
Y=polcoeff(v,1);
r=concat(r,[[X,Y]]);
);
return(r);
}
bnfcertify
solves the case for GRH.
$\endgroup$