# number of solutions to $x^2 + xy + y^2 = 0\mod p$

Let $$p$$ be an odd prime congruent to $$2$$ modulo $$3$$ and $$c$$ an integer between $$1$$ and $$p-1$$. Let $$\chi(x)$$ denote $$\left(\dfrac{x}{p}\right)$$ (the Legendre symbol modulo $$p$$ for $$x$$). How many solutions $$(x,y)$$ are there to $$x^2 + xy+y^2 = c$$ where $$0\leq x,y < p$$?

How many are there when $$0\leq x < y < p$$?

Evaluate $$\prod_{0\leq x (both when $$p\equiv 3\bmod 4$$ and $$p\equiv 1\bmod 4$$).

I know that modulo p, the solutions to a quadratic congruence $$ax^2 + bx + c\equiv 0, a\neq 0,$$ exist if and only if $$b^2 - 4ac \equiv y^2$$ has a solution (for y). Also, if $$x=0$$ there are only $$\chi(c)$$ solutions. Similarly there are $$\chi(c)$$ solutions if $$y=0$$. But I'm not sure how to find the number of solutions for arbitrary nonzero $$x,y$$. Also, by the first two questions, one can simplify the product to $$\prod_{c=1}^{p-1} c^{f(c)},$$ where $$f(c)$$ is the number of times $$c$$ appears as $$x^2 + xy + y^2$$ modulo $$p$$. $$x^2 + xy+y^2 \equiv 0\mod p\Rightarrow (x+y)^2 \equiv xy \mod p,$$ so it's not clear that the product in question is even nonzero.

• Making $u=\dfrac xy$ you have $u^2+u+1=0$ modulo $p$ with, $p$ prime,and this equation is soluble if and only if $p\equiv 1\pmod3$ and when $p=3$ Commented Aug 16, 2022 at 1:16

Edit: there was a mistake in my calculation. I hope I fixed it now. More edits: simplified the computation.

The curve $$C_{c,p}$$ over $$\mathbb{F}_p$$ defined by $$x^2+xy+y^2=c$$ is a conic, so if it is smooth and absolutely irreducible its completion in the projective plane will contain $$p+1$$ points. But we can also go another route: over the field $$\mathbb{F}_{p^2}$$, we can factor the equation as $$(x-y\omega)(x-y\omega^2)=c$$, with $$\omega$$ a primitive third root of unity (which is not contained in $$\mathbb{F}_p$$ since $$p \equiv 2 \pmod{3}$$). Now if $$x,y \in \mathbb{F}_p$$, notice that the product $$(x-y\omega)(x-y\omega^2)$$ can be written $$(x - y\omega) \cdot \operatorname{Frob}(x-y\omega)$$, in other words this is the field norm of the element $$x-y\omega$$ for the field extension $$\mathbb{F}_p \subset \mathbb{F}_{p^2}$$, so we are in fact looking for the number of elements $$x-y\omega \in \mathbb{F}_{p^2}$$ such that their norm equals $$c$$. The norm of an element $$\xi$$ equals $$\xi \cdot \operatorname{Frob}(\xi)=\xi^{p+1}$$, so we are really solving the equation $$\xi^{p+1}=c$$ over $$\mathbb{F}_{p^2}$$. It is easy to see this has $$p+1$$ solutions: the multiplicative group $$\mathbb{F}_{p^2}^{\times}$$ is cyclic of order $$(p+1)(p-1)$$, whereas the order of $$c$$ must divide $$p-1$$ because $$c \in \mathbb{F}_p^{\times}$$. Therefore the answer to the first question is that there are $$p+1$$ solutions.

The second question has for its answer $$(p+1-a)/2$$, where $$a$$ is the number of solutions of $$x^2+xy+y^2=c$$ with $$x=y$$. Evidently we have $$a=\chi(3c)+1$$, so that the answer to the question is $$(p-\chi(3c))/2$$.

For the third question, first note the product is non-zero since $$x^2+xy+y^2=0$$ would imply $$(x-y\omega)(x-y\omega^2)=0$$, contradicting the existence of a primitive third root of unity in $$\mathbb{F}_p$$. Then, since $$f(c)$$ equals $$(p-\chi(3c))/2$$, the exponent in the formula $$\prod_c c^{f(c)}$$ which you found really assumes only two values, namely $$(p+1)/2$$ and $$(p-1)/2$$. So if we denote by $$A$$ the set of $$c$$ such that $$\chi(3c)=-1$$, and by $$B$$ the set of $$c$$ such that $$\chi(3c)=1$$, then the product $$\prod_c c^{f(c)}$$ equals $$\prod_{c \in A} c^{(p+1)/2} \prod_{c \in B} c^{(p-1)/2}$$. Note that $$\chi(3) = (-1)^{(p-1)/2} \left( \frac{p}{3} \right) = -(-1)^{(p-1)/2}$$ since $$p \equiv 2\pmod{3}$$. So, by the multiplicativity of $$\chi$$, we can also describe $$A$$ as the set of values $$c$$ such that $$\chi(c)=-\chi(3)=(-1)^{(p-1)/2}$$, so that $$B$$ equals the set of values $$c$$ with $$\chi(c)=(-1)^{(p+1)/2}$$. We will evaluate the two factors of the product as follows:

The easiest thing to do is rewrite the expressions over which the products are taken in terms of a generator $$g$$ of the multiplicative group of $$\mathbb{F}_p$$. An element $$c \in A$$ has the general form $$g^{(p-1)/2} g^{2k} = -g^{2k}$$, since we said that $$A$$ is the set of values $$c$$ such that $$\chi(c)=(-1)^{(p-1)/2}$$, and where we have used $$\chi(g)=g^{(p-1)/2}=-1$$. So the product indexed by $$A$$ then becomes $$\prod_{k=1}^{(p-1)/2} (-1)^{(p+1)/2} g^{k(p+1)}$$. Likewise, the general form of an element of $$B$$ is $$g^{(p+1)/2} g^{2k} = -g^{2k+1}$$, making the product indexed by $$B$$ equal to $$\prod_{k=1}^{(p-1)/2} (-1)^{(p-1)/2} g^{(2k+1)(p-1)/2}$$.

So taking the two products together, we are reduced to the computation of the product $$\prod_{i=1}^{(p-1)/2} -g^{k(p+1)} g^{(2k+1)(p-1)/2}$$, which equals $$\prod_{i=1}^{(p-1)/2} -g^{k(p+1)} g^{k(p-1)} g^{(p-1)/2}$$. The minus sign cancels the factor $$g^{(p-1)/2}=-1$$, so this also equals $$\prod_{i=1}^{(p-1)/2} g^{2kp}$$, which equals $$g^{\sum_{i=1}^{(p-1)/2} 2kp} = g^{p(p^2-1)/4}.$$ Using $$g^p=g$$ and once again that $$g^{(p-1)/2}=-1$$, we finally get that this equals $$(-1)^{(p+1)/2}$$, which equals $$-\left( \frac{-1}{p} \right)$$.

• I still think your approach is fairly complicated. Tbh, I'm much better at elementary number theory than I am with field/galois theory (I only actually know some ring theory and group theory). So if possible, could you elaborate on how exactly you're defining your field extension? Is $\mathbb{F}_{p^2}$ just the set $\{ a + b\omega : a,b \in F_{p}\}$? Frob(x) gives the complex conjugate of x. But even with this defined, I'm not sure how to show $a+b\overline{omega} = (a+b\omega)^p$ (or maybe this isn't even true). Commented Aug 16, 2022 at 14:08
• Yes, that last statement is indeed true. It follows from the fact that $\operatorname{Frob}$ acts transitively on the set of conjugates of $\omega$ over $\mathbb{F}_p$. It could be worth your while to spend some time learning finite field theory. It's not really Galois theory, or maybe a better way to say it is that the Galois theory for finite fields is a lot easier than the general case. You are right that this is still not a trivial answer to your question, but I don't know if there really exists a much easier one.
– R.P.
Commented Aug 16, 2022 at 14:12
• In any case, knowing the properties of the Frobenius map is tremendously useful when dealing with finite fields. By the way, proving $(a + b\omega)^p = a + b\overline{\omega}$ is actually easy to do directly: $(a + b\omega)^p=a^p + b^p \omega^p$ by the "freshman's dream" theorem, which equals $a + b \omega^p$ because the $p$-th-power map acts trivially on $\mathbb{F}_p$. Now since $p \equiv 2 \pmod{3}$, we have $\omega^p=\omega^2$, showing that $\omega^p$ is the unique primitive root of unity distinct from $\omega$, which you denote $\overline{\omega}$.
– R.P.
Commented Aug 16, 2022 at 14:15
• Also I was just about to point out that proving my last claim would've been trivial; from a number theory perspective it's just modular arithmetic and it involves the fact that ${p\choose i}$ is divisible by p for $1\leq i < p$ when $p$ is prime. I think that one can also show directly that $(a+b\omega)^{p^2 - 1} = 1$ for every $a,b\in F_p$. It is now clear that $(a+b\omega)^{p^2} = (a+b\omega^2)^p = a + b\omega.$ Taking inverses of both (in $\mathbb{C}$), we get $(a+b\omega)^{p^2 - 1} = 1.$ Commented Aug 16, 2022 at 14:34
• Not in $\mathbb{C}$, only in $\mathbb{F}_{p^2}$ (or any field extension of $\mathbb{F}_{p^2}$, but that would still have characteristic $p$).
– R.P.
Commented Aug 16, 2022 at 14:39