Diophantine equation $x^2-dy^2=k$ in $\mathbb{Z}_n$

Question

Does anyone know when $x^2-dy^2=k$ is resoluble in $\mathbb{Z}_n$ with $(n,k)=1$ and $(n,d)=1$ ? I'm interested in the case $n=p^t$

Answer 1

Suppose first that $n=p$ is an odd prime (I won't deal with even $n$ in this solution - the ideas will be similar). If $k$ is a quadratic residue modulo $p$, then there is a solution with $y=0$ even. If $d$ is a quadratic residue modulo $p$, then the left-hand side factors as $x^2-dy^2 = (x-cy)(x+cy)$ for some $c$; then you can set for example $x\equiv(k+1)2^{-1}\pmod p$ and $y\equiv(k-1)(2c)^{-1}\pmod p$, so that $x+cy\equiv k\pmod p$ and $x-cy\equiv1\pmod p$.

If both $d$ and $k$ are quadratic nonresidues modulo $p$, then the number of solutions to $x^2-dy^2=k$ is exactly equal to $p + \sum_{y=1}^p \big( \frac{k+dy^2}p \big)$, using the Legendre symbol. That sum is always equal to 1, hence the number of solutions is $p+1$, which is positive. (I'd appreciate a commenter giving a reference for this fact. The other cases can be done using these ideas as well, but I thought the elementary solutions were illuminating.)

So $x^2-dy^2\equiv k\pmod p$ always has a solution. But then in the case $n=p^t$, we see by Hensel's lemma that $x^2-dy^2\equiv k\pmod{p^t}$ always has a solution for every $t\ge1$.

(By the Chinese remainder theorem, if there's a solution modulo every prime power, then there's a solution modulo every integer.)

Answer 2

It is too long for the comment so I will post it as an answer. There is a more elementary way to show that $x^2-dy^2=k$ has a solution $(\mod p),$ for odd prime $p.$ As Greg mentioned above the Chinese remainder theorem and Hensel's lemma imply the result afterwards.

To see that, note that the set $A=\{x^2(\mod p),\ \ \ \ \ x=\overline{0,\frac{p-1}{2}}\}$ contains exactly $\frac{p+1}{2}$ elements. Indeed, if $x^2=y^2(\mod p),$ then $(x-y)(x+y)$ is divisible by $p,$ and since $x+y<p,$ $x=y.$ By analogy the set $B=\{dy^2+k(\mod p),\ \ \ \ \ y=\overline{0,\frac{p-1}{2}}\}$ has exactly $\frac{p+1}{2}$ elements. By the Pigeonhole, $A$ and $B$ must have at least one element in common and the result follows.