Decidir una ecuación diofantina cuadrática

Question

Dado $a,b\in\Bbb Q_+$ ¿hay una manera fácil de decidir si $$S_{a,b}=\{(x,y)\in\Bbb Z^2:ax^2 + by^2=1\}=\emptyset?$$

Estoy más interesado en ver si hay una forma rápida de probar el caso cuando las soluciones no existen.

Answer 1

Es mejor escribirlo como $ax^2+by^2=c$ con $a,b,c\in\mathbb{Z}$ . Su suposición de que $a$ y $b$ son positivos implica que hay una solución real. Así que ahora se puede utilizar el teorema de Legendre (criterio), que dice que $ax^2+by^2+cz^2=0$ (con $a,b,c$ enteros no nulos, libres de cuadrados, relativamente primos entre sí y no todos positivos o negativos) tiene una solución no trivial en enteros si y sólo si $$ \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. $$ Así que todo se reduce a comprobar estos tres símbolos de residuos cuadráticos. Lo que realmente ocurre es que una ecuación polinómica cuadrática tiene solución en enteros si y sólo si tiene una solución real y una $p$ -solución de la caducidad para todos $p$ .

Para una demostración del teorema de Legendre, véase por ejemplo Introducción clásica a la teoría moderna de los números , Irlanda y Rosen, capítulo 17, sección 3.

Answer 2

Creo que lo mejor es escribir la ecuación $ax^2+by^2=c$ con $a,b,c$ enteros positivos con $gcd(a,b,c)=1$ .

Permítanme primero darles un algoritmo lento: ya que $a,b$ son positivos una solución debe satisfacer $x^2\le c/a$ y $y^2\le c/b$ para que pueda enumerar estos posibles $x$ y $y$ y ver si encuentra una solución. Un poco mejor, sólo enumerar el $y$ (o $x$ ) y comprobar si $c-by^2$ es divisible por $a$ y el cociente es un cuadrado.

Esto es lo que se puede hacer en el caso especial $a=1$ : $x^2+by^2$ es la forma de la norma del orden cuadrático imaginario $\mathbb{Z}[\sqrt{-b}]$ . Después de factorizar $c$ se puede escribir la lista de ideales de la norma $c$ . La resolubilidad de la ecuación es entonces equivalente a la principalidad de uno de estos ideales. Esto se puede comprobar calculando los vectores más cortos del ideal para la forma cuadrática de la norma, lo que se puede hacer en tiempo polinómico. Sospecho que hay un algoritmo similar en el caso general $a\neq 1$ pero no lo he resuelto.

---

Editar: Su segunda ecuación $ax^2+by=c$ ( $a,b,c$ enteros) es más sencillo. Si $x$ está dada, hay una solución $y$ si y sólo si $ax^2=c \pmod{b}$ . Así que debe tener en cuenta $b$ y, a continuación, comprueba si $ca^{-1}$ es un cuadrado módulo $b$ y encontrar todas las raíces cuadradas posibles, y finalmente todas las soluciones vienen dadas por la toma de todas las elevaciones de esas raíces y las correspondientes $y$ .

Answer 3

Creo que pari/gp puede resolver esto a través de bnfisintnorm .

Para los enteros, $a,b,c$ , usted está resolviendo $ax^2+by^2=c$ con $ab$ >0.

Resolver simbólicamente:

$$ x= \pm {\frac {\sqrt {-a \left( b{y}^{2}-c \right) }}{a}} $$ .

El denominador es entero, por lo que el numerador debe ser entero divisible por $a$ .

Elevando al cuadrado el numerador obtenemos:

$$ X^2+aby^2=ac \qquad(1) $$

Desde $ab>0$ (1) tiene un número finito de soluciones y es similar a Pell, ya que es mónico en $X$ .

No hay unidades en el campo numérico con polinomio definidor $X^2+ab$ , así que pari's bnfisintnorm(K,ac) dará soluciones y usted debe encontrarlas $X$ divisible por $a$ .

---

Prototipo de aplicación pari

 {
 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);
 }