Counting solutions of a cubic congruence using Gauss sums
In the introduction to André Weil's Number of solutions of equations in finite fields he mentions article 358 of Gauss' Disquisitiones. Can someone please show me the connection here:
How does the Gaussian sum of order $3$, for primes of the form $p = 3n+1$ determine the number of solutions for all congruence $ax^3 - by^3 = 1 \pmod p$?
By ignoring a small subcase ($c = 0$ or $d = 0$), we can count the solutions for $cd \neq 0$ by the sum $\displaystyle \sum_{\stackrel{c+d = 1}{c,d \neq 0}} \#\{x:ax^3 = c\} \times \#\{y: -by^3 = d\} ... (*)$.
Expressing the term in this sum, using multiplicative characters:
Now we look at $\{x: x^3 = u\}$ for some $u$, and we want to calculate its size. This can be interpreted as a sum of cubic characters: $\chi(u) + \chi^2(u) + \chi^3(u)$, where $\chi$ is a cubic character on $\mathbb{Z}/p\mathbb{Z}$, i.e. $\chi \neq 1$, but $\chi^3 = 1$. Now where does this interpretation come from?
If $x^3 = u$ has one solution, it has 3 because $p \equiv 1 \pmod{3}$ tells us that 1 has 3 cube roots in $\mathbb{Z}/p\mathbb{Z}$. On the character side, if $u$ is a cube of something, using $\chi^3 = 1$ w see that $\chi(u) + \chi^2(u) + \chi^3(u) = 3$.
If $x^3 = u$ has no solution, then notice that $\chi(u) \neq 1$. Then if we write $S = \chi(u) + \chi^2(u) + \chi^3(u)$, note that $\chi(u)S = \chi(u)$, which means $S = 0$.
So how does this interpretation in terms of characters help? Plug in the character sums in (*). We are going to have a lot of cross terms. These cross terms can be splitted into sums of Jacobi sums, which are closely related to Gauss sums. (See Koblitz' Introduction to Elliptic Curves and Modular forms Section 2.2, or Ireland and Rosen's A Classical Introduction to Modern Number Theory)
The situation here:
In our case, $(*) = \sum_{c+d = 1, c,d \neq 0} \left(1 + \chi(c/a) + \chi^2(c/a)\right)\left(1 + \chi(-d/b) + \chi^2(-d/b)\right)$. There are three types of sum in the expansion. I would do one in each type to show you how it feels like.
$\displaystyle \sum_{c+d = 1, c,d \neq 0} 1 = p-2$, since $c$ can't be 0 or 1 and can be everything else.
$\displaystyle \sum_{c+d = 1, c,d \neq 0} \chi(c/a) = -\chi(1/a)$. To show this, note that for a nontrivial character $\chi$, $\displaystyle \sum_{u \in \mathbb{Z}/p\mathbb{Z}} \chi(u) = 0$, by an argument similar to what we showed in step 2 in the last block.
$\displaystyle \sum_{c+d = 1, c,d \neq 0} \chi(c/a) \psi (-d/b)$, where $\psi = \chi$ or $\chi^2$. This is the one we need Jacobi sums $\displaystyle J(\chi, \psi) = \sum_{x \in \mathbb{Z}/p\mathbb{Z}} \chi(x)\psi(1-x)$. Note that
$\displaystyle \sum_{c+d = 1, c,d \neq 0} \chi(c/a) \psi (-d/b) = \chi(1/a)\psi(-1/b) J(\chi, \psi)$
and that if you check out the books I mentioned before, $J$ can be expressed by Gauss sums of $\chi$ or $\chi^2$.
Summary:
So after all these work, we can find $\displaystyle \sum_{\stackrel{c+d = 1}{c,d \neq 0}} \#\{x:ax^3 = c\} \times \#\{y: -by^3 = d\} $ in terms of Gauss sums. There remains the case $c = 0$ or $d = 0$, which is easy to do directly. Sum them up, and you get the answer. The two books I mentioned both have examples of these types, so you may want to read them.