Let $N$ be the number of solutions of the congruence $x^n \equiv a \bmod p$, $p$ an odd prime. Assume that $n | (p-1)$ and $p \nmid a$. How do I show that $$N=\sum_{\chi^n=\chi_0}\chi(a)$$
1 Answer
There's certainly a neater solution, but this works:
Let $U=(\mathbf{Z}/p\mathbf{Z})^\times$. Write $a=\xi^\alpha$ where $\xi$ is a primitive root. Then, since $n \mid |U|$, the equation $x^n-a=0$ has a solution if and only if $n\mid \alpha$; moreover, if $u$ is such a solution, then $\{\xi^{j(p-1)/n}u : 0 \leq j <n\}$ is a full set of solutions. Hence there are either $n$ or $0$ solutions, according as to $n \mid \alpha$ or not.
On the other hand, we have $$\sum_{\chi^n=\chi_0}\chi(a) = \sum_{\chi^n=\chi_0}\chi(\xi)^\alpha.$$
Now the set of all $\chi$ such that $\chi^n = \chi_0$ has precisely $n$ elements since $U \simeq \hat U$ is cyclic and $n\mid |U|$. They are given by $\xi \mapsto e^{2\pi i j/n}$, $0 \leq j <p-1$. Hence
$$\sum_{\chi^n=\chi_0}\chi(\xi)^\alpha = \sum_{0 \leq j <p-1}e^{2\pi i \alpha j/n}$$
This is the sum of all $(n/(n,\alpha))^{th}$ roots of unity, taken $(n,\alpha)$ times. Hence it is $0$ if $n \nmid \alpha$, and $n$ otherwise.