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 <y < p}(x^2 + xy + y^2)\mod p$ (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.

  • 1
    $\begingroup$ 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$ $\endgroup$
    – Piquito
    Aug 16, 2022 at 1:16

1 Answer 1


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)$.

  • $\begingroup$ 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). $\endgroup$
    – Gord452
    Aug 16, 2022 at 14:08
  • $\begingroup$ 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. $\endgroup$
    – R.P.
    Aug 16, 2022 at 14:12
  • $\begingroup$ 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}$. $\endgroup$
    – R.P.
    Aug 16, 2022 at 14:15
  • $\begingroup$ 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.$ $\endgroup$
    – Gord452
    Aug 16, 2022 at 14:34
  • $\begingroup$ 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$). $\endgroup$
    – R.P.
    Aug 16, 2022 at 14:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .