Ecuación diofántica$x^2-dy^2=k$ en$\mathbb{Z}_n$

Question

¿Alguien sabe cuándo$x^2-dy^2=k$ se puede resolver en$\mathbb{Z}_n$ con$(n,k)=1$ y$(n,d)=1$? Estoy interesado en el caso$n=p^t$

Answer 1

Supongamos primero que $n=p$ es una extraña prime (no voy a tratar incluso con $n$ en esta solución, las ideas serán similares). Si $k$ es un residuo cuadrático módulo $p$, entonces no es una solución con $y=0$ incluso. Si $d$ es un residuo cuadrático módulo $p$, entonces el lado izquierdo factores como $x^2-dy^2 = (x-cy)(x+cy)$ algunos $c$; entonces se puede establecer, por ejemplo,$x\equiv(k+1)2^{-1}\pmod p$$y\equiv(k-1)(2c)^{-1}\pmod p$, por lo que el$x+cy\equiv k\pmod p$$x-cy\equiv1\pmod p$.

Si tanto $d$ $k$ son cuadrática nonresidues modulo $p$, entonces el número de soluciones a $x^2-dy^2=k$ es exactamente igual a $p + \sum_{y=1}^p \big( \frac{k+dy^2}p \big)$, utilizando el símbolo de Legendre. Esa suma es siempre igual a 1, por lo tanto el número de soluciones es $p+1$, lo cual es positivo. (Te agradecería un comentario dando una referencia de este hecho. El resto de los casos se puede hacer uso de estas ideas, pero creo que la primaria soluciones fueron esclarecedores.)

Por lo $x^2-dy^2\equiv k\pmod p$ siempre tiene una solución. Pero, a continuación, en el caso de $n=p^t$, vemos por Hensel del lema que $x^2-dy^2\equiv k\pmod{p^t}$ siempre tiene una solución para cada $t\ge1$.

(Por el teorema del resto Chino, si no hay una solución cada modulo de potencia principal, entonces hay una solución modulo cada entero).

Answer 2

Es demasiado largo para el comentario, así que voy a publicar como una respuesta. Hay más elemental forma de mostrar que la $x^2-dy^2=k$ tiene una solución $(\mod p),$ por extraño prime $p.$ Como Greg mencionado anteriormente, el teorema del resto Chino y Hensel del lema implica el resultado después.

A ver que, tenga en cuenta que el conjunto de $A=\{x^2(\mod p),\ \ \ \ \ x=\overline{0,\frac{p-1}{2}}\}$ contiene exactamente $\frac{p+1}{2}$ elementos. De hecho, si $x^2=y^2(\mod p),$ $(x-y)(x+y)$ es divisible por $p,$ y ya $x+y<p,$ $x=y.$ Por analogía, el conjunto $B=\{dy^2+k(\mod p),\ \ \ \ \ y=\overline{0,\frac{p-1}{2}}\}$ tiene exactamente $\frac{p+1}{2}$ elementos. Por el Palomar, $A$ $B$ debe tener al menos un elemento en común y el resultado de la siguiente manera.