The number of solutions $(x,y)$ of the congruence $n \equiv X^2-XY+Y^2$ (mod $p^\alpha$).

Question

Is there general formula of the solutions of the congruence? \begin{equation} n\equiv X^2-XY+Y^2 \pmod r, \end{equation} where $n\in\Bbb Z$ and $r\in\Bbb N$.

If we define an arithmetic function (two variables or one variable with fixed $n$) \begin{equation} N(n,r):=|\{(x,y)\in\Bbb Z^2:x^2-xy+y^2\equiv n\pmod r,0\leq x,y< r\}|. \end{equation}

I know that such function is multiplicative in $r$.

I have no approach for this question. Please give me a hint to solve this problem, or let me know that related something. Thanks.

Answer 1

So far, just an answer when $r=3^a.$

When $r$ is odd, this can be multiplied by $4$ to get $$(2X-Y)^2+3Y^2\equiv 4n\pmod r$$

Then solutions to $Z^2+3Y^2\equiv 4n$ are in $1-1$ correspondence with your congruence.

If $r=3^a,$ then:

1. If $n\equiv 1\pmod 3,$ there is two solutions for every $Y, $ for $N(n,3^a)=2r$ solutions total.
2. If $n\equiv 2\pmod 3,$ then there are no solutions, so $N(n,3^a)=0.$
3. What if $n\equiv0\pmod3?$ If $a=1,$ then $N(n,3)=3.$ If $a\geq2,$ then $3\mid Z.$ Then the number of solutions is three times the number of solutions to $$3Z_1^2+Y^2\equiv 4n/3\pmod{3^{a-1}},$$ since there are three $Y$ modulo $3^{a+1}$ for every $Y$ modulo $3^{a}.$ So $N(3n,3^{a+1})=3N(n,3^a)$

So, if $r=3^a,$ $n=3^kn’,$ with $\gcd(n’,3)=1,$ then:

$$N(n,3^a)=\begin{cases}3^a&k\geq a\\2\cdot 3^a&k<a,n’\equiv 1\pmod 3\\0&k<a,n’\equiv 2\pmod 3\end{cases}$$ Not sure what to do with the case $r=2^a.$

Nor yet the case $r=p^a$ when $p>3.$