Number of solution in cubic residue I need to find the number of non zero solutions in $\mathbf Z_p $ to the equation $x+y=1,$ where $x\in \Gamma$ and $y\in g\Gamma$ where $ g $ is primitive root modulo an odd prime $p$ and $\Gamma=\langle g^3\rangle$. I could do it when both $x$ and $y$ are in $\Gamma$.
Clearly, it is equivalent to solving $g^{3k_1}+g^{3k_2+1}=1$ for $k_1$ and $k_2$. I have tried a few ways but nothing promising . Kindly help.
 A: Let's count the solutions with $x \in \Gamma$ and $y \in g^n \cdot \Gamma$ as $n$ varies; it should only depend on $n \mod 3$.
Naturally $p \equiv 1 \mod 3$, so write $p-1=3m$ with $m$ even, so $(-1)^m = 1$.
We have:
$$\frac{1}{|\Gamma|} \sum_{x \in \Gamma} x^k = \begin{cases} 1, & k \equiv 0 \mod m, \\
0, & \text{otherwise},  \end{cases}$$
$$\frac{1}{|\Gamma|} \sum_{y \in g^n \Gamma} y^k = \begin{cases} g^{nk}, & k \equiv 0 \mod m, \\
0, & \text{otherwise}. \end{cases} $$
Moreover, by Fermat's Little Theorem, $1 - (x+y-1)^{p-1} = 0$ if $x+y=1$ and $0$ otherwise. Of course, $1/|\Gamma| = 3/(p-1) \equiv -3 \mod p$.
Let $S = S_n$ denote the set of solutions. Then
$$\begin{aligned}
9|S| = & \ 9 \sum_{S} 1 \\
 \equiv & \ \frac{1}{|\Gamma|^2} \sum_{S}  1  \mod p \\
= & \ \frac{1}{|\Gamma|^2} \sum_{x \in \Gamma,y \in g \Gamma} 1 - (x+y-1)^{p-1} \\
= & \ \frac{1}{|\Gamma|^2} \sum_{x \in \Gamma,y \in g \Gamma} 1 - \sum_{a+b+c=p-1}
x^a y^b (-1)^c \binom{p}{a,b,c} \\
= & \ \frac{-1}{|\Gamma|^2} \sum_{x \in \Gamma,y \in g \Gamma}  \sum_{a+b+c=p-1}^{(a,b,c) \ne (0,0,3m)}
x^a y^b (-1)^c \binom{p}{a,b,c} \\
= & \  -  \sum_{a+b+c=p-1}^{(a,b,c) \ne (0,0,3m)}  \frac{1}{|\Gamma|^2} \sum_{x \in \Gamma,y \in g \Gamma}
x^a y^b (-1)^c \binom{p}{a,b,c} \\
 \end{aligned}$$
The inner sum is zero unless $a \equiv b
\equiv c \equiv 0 \mod m$, or equivalently if
$$(a,b,c) \in (3m,0,0), (2m,m,0), (2m,0,m), (m,2m,0), (m,m,m), (m,0,2m), (0,3m,0), (0,2m,m), (0,m,2m).$$
If we collect the $6$ terms of the form $[0,m,2m]$ up to re-ordering, we get
$$\binom{3m}{0,m,2m}(1 + 1 + g^{mn} + g^{mn} + g^{2mn} + g^{2mn}).$$
If $(n,3) = 1$, then $g^{mn}$ is a non-trivial $3$rd root of unity $\omega \mod p$, so this vanishes,
since $1 + \omega + \omega^2 = 0$.
I  $3|n$, then $g^{mn} = 1$, so this is
$$6 \frac{(3m)!}{m! (2m)!}  \equiv 6 \mod p,$$
since $m! = 1 \cdot 2 \cdot \ldots \cdot m  \equiv (-1)^m (3m)(3m-1)\ldots (2m+1)$,
so $m! (2m)! \equiv (-1)^m (3m)! \equiv (3m)! \mod p$.
If we collect the two remaining terms of the form $[0,0,3m]$ we get $-1-1=-2$. Putting this together, we get
$$9|S_n| \equiv 
\begin{cases} \displaystyle{ - 2 - \frac{(3m)!}{m!^3} g^{mn}}, & (3,n) = 1, \\
\displaystyle{-8 -  \frac{(3m)!}{m!^3}}, & n| 3, \end{cases} \mod p$$
As a test case, if we add up the three possibilities, we get
$$9 (|S_1| + |S_2| + |S_3|) \equiv - 12 \mod p.$$
On the other hand, the left hand side can be computed; for any $x \in \Gamma$,
there is a $y = 1- x$ which is either in $\Gamma$, $g \Gamma$, or $g^2 \Gamma$ unless $x = 1$.
So the LHS is
$$9 (|\Gamma| - 1) = 9 \cdot \frac{(p-4)}{3} = 3p - 12 \equiv -12 \mod p.$$
At this point we have computed $|S_n| \mod p$. But we can use this to compute $|S_n|$ as well,
using the Weil conjectures.That is because $9 |S_n|$ is more or less the number of points on the
curve
$$X_n:=x^3 + g^n y^3 = 1.$$
That is because each element of $|S_n|$ when $p \equiv 1 \mod 3$ gives $9$ points on this curve
(multiplying either $x$ or $y$ by $\omega$), and conversely an orbit of points gives an element of $|S_n|$
unless $xy =0$, which is at most $6$ points. So we have a formula for $9 |S_n| \mod p$, and then we have from
the Weil conjectures
$$|X_n(\F_p) - p - 1| \le 2 \sqrt{p}, \qquad 0 \le X_n(\F_p) - 9 |S_n| \le 6.$$
Equivalently, $9|S_n|$ is given modulo $p$, but then it is the integer that is this value modulo $p$ and is closest to $p$.
