¿Existen ecuaciones Pell $x^2 - dy^2 = n$ que son fáciles de resolver?

Question

Considere la ecuación Pell $x^2 - dy^2 = n$ donde $d$ es un entero positivo no cuadrado.

¿Existen ejemplos de $d$ que facilita la resolución (obtención de soluciones no triviales) de la ecuación para cualquier $n \in Z - \{ 0 \} $ ?

Nota: Para aclarar la motivación de esta pregunta, he $n$ que debe representarse en forma de Ecuación Pell Generalizada $(x^2 - dy^2)$ . Si podemos elegir libremente $d$ positivo no cuadrado, podemos hacer elección(es) para $d$ , tal vez en función de $n$ (ya que algunas opciones de $d$ , $n$ no permiten soluciones), que hace que la ecuación sea fácilmente resoluble.

Vea lo relacionado: Es cada número entero $z$ representable en forma Pell como $x^2 \pm dy^2 =z$ ?

Answer 1

Esto se denomina ecuación de Pell generalizada . Como en el caso clásico existe un algoritmo, basado en fracciones continuas simples, debido a Lagrange, que resuelve $$ x^2-dy^2=n $$ para cualquier cuadrado libre dado $d$ y dado $n\in \Bbb Z\setminus \{0\}$ .

Referencia: Sección $6$ de Keith Conrad notas .

Yo no llamaría a este algoritmo "trivial", pero ciertamente es bien conocido y fácil de realizar. Para las pequeñas $d$ como $d=2$ puede ser un poco más rápido, pero sigue sin ser trivial.

Answer 2

Para cualquier $d$ hay teoremas que te dicen qué valores de $n$ son representables. Véase https://en.wikipedia.org/wiki/Binary_quadratic_form .

En particular, cuando $d=-1$ una prima $n$ es una suma de cuadrados si y sólo si es congruente con $1$ modulo $4$ . Incluso en ese caso más sencillo, encontrar los cuadrados que suman $n$ no es fácil: ver https://stackoverflow.com/questions/5380323/whats-the-fastest-algorithm-to-represent-a-prime-as-sum-of-two-squares .

Así que la respuesta a su pregunta es "no".

Answer 3

Puede responder negativamente si puede demostrar que $n$ no es un cuadrado perfecto, módulo $d.$ Esto es más fácil de hacer si se puede factorizar primariamente $d.$ si no, sólo se puede utilizar el símbolo de Jacoby, que, si devuelve $-1,$ demuestra que $n$ no es un cuadrado módulo $d,$ pero un valor de $1$ no significa que lo sea.

---

Cuando $n>0,$ puede encontrar un máximo $x$ para comprobar, y resolver el problema en un tiempo finito.

Primero resuelve para $a^2-db^2=1$ para el número entero más pequeño $a\geq 1$ y el correspondiente positivo $b.$

Entonces, si $$x^2-dy^2=n\tag{1}$$ tiene una solución, tiene una solución con: $$x\leq \sqrt{\frac{n(a+1)}{2}}$$

Esto se debe a que si $(x,y)$ es una solución positiva de (1), entonces también lo es $(xa-ydb,ay-xb).$

Ahora, si $-x<xa-ydb<x$ entonces tenemos una solución para un positivo menor $x.$ Y eso ocurre si:

$$x(a+1)>ydb>x(a-1)$$

Todos los términos son positivos, así que podemos elevar al cuadrado ambos lados:

$$x^2(a+1)^2>y^2d^2b^2>x^2(a-1)^2$$

Sustituyendo $dy^2=x^2-n$ lo consigues:

$$x^2(a+1)^2>db^2(x^2-n)>(a-1)^2x^2.$$

Ahora, $db^2=a^2-1.$ Restando $db^2x^2$ de ambos lados te da:

$$x^2(2a+2)>-n(a^2-1)>(2-2a)x^2.$$

Desde $x^2(2a+2)$ es siempre positivo, y $-n(a^2-1)$ es negativo, la primera desigualdad es siempre cierta.

Así que si $$\frac{n(a+1)}2=\frac{n(a^2-1)}{2(a-1)}<x^2$$ entonces podemos encontrar un positivo menor $x.$

Así que si hay una solución, debe haber una solución con $$2\leq x \leq\sqrt{\frac{n(a+1)}{2}}$$

---

Creo que, por $n<0$ puede mostrar que debe haber una solución con:

$$2\leq x \leq \sqrt{\frac{-n(a-1)}2}$$

---

Por supuesto, $a$ puede ser muy grande. Cuando $d=97,$ $a= 1766319049.$

---

En realidad es más fácil comprobar $y.$ Sólo tienes que comprobarlo:

$$1\leq y\leq\sqrt{\frac{n(a-1)}{2d}}$$ cuando $n>0,$ y

$$1\leq y\leq\sqrt{\frac{-n(a+1)}{2d}}$$ cuando $n<0.$

Answer 4

He desarrollado una función de una sola variable que genera Números Pell en secuencia.

\begin{equation}\quad m=k+\sqrt{2k^2+(-1)^k}\end{equation} A partir de cero, cada valor de $k$ genera un número entero $m$ que es el siguiente número Pell. Aquí hay muestras (empezando por $1$ ) que utilizaba para generar triples pitagóricos donde $B=A\pm1$ . \begin{align*} k=1\quad &\implies m=(1+\sqrt{2(1)^2+(-1)^1}\space)\big)=2\quad & F(2,1)=(3,4,5)\\ k=2\quad &\implies m=(2+\sqrt{2(2)^2+(-1)^2}\space)\big)=5\quad & F(5,2)=(21,20,29)\\ k=5\quad &\implies m=(5+\sqrt{2(5)^2+(-1)^5}\space)\big)=12\quad & F(12,5)=(119,120,169)\\ k=12\quad &\implies m=(12+\sqrt{2(12)^2+(-1)^{12}}\space)\big)=29\quad & F(29,12)=(697,696,985) \end{align*}

También puede generar un número Pell $(P)$ directamente utilizando esta fórmula. \begin{equation} P_n= \frac{(1 + \sqrt{2})^n - (1 - \sqrt{2})^n}{2\sqrt{2}}\qquad n\ge0 \end{equation}

Se producirá $\quad P_0=0\quad P_=1\quad P_2=2\quad P_3=5\quad P_4=12\quad P_5=29\quad P_6=70\quad ...$

Esta es la segunda fórmula después de la línea que dice "probado usando series telescópicas" en el enlace de los números Pell arriba y parece ser la más fácil de usar de las que he probado.