Past exam of the options II course of the University of Oxford / 2010 / C (Number Theory)

A primitive root modulo $p$ is a residue class generating the cyclic multiplicative group $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, so its order is $p-1$. If $g$ is one generator, all generators are $g^j$ with $\gcd (j,p-1)=1$. Thus the number iswhere $\phi$ is Euler's totient function. This includes $p=2$, with $\phi (1)=1$.

For $n\ge 1$, the zero residue contributes zero. Write $S={\sum }_{x\in {\mathbb{F}}_p^{\times }}{x}^n$. Multiplication by any nonzero $\alpha$ permutes these residues, so $S={\alpha }^{n}S$ in ${\mathbb{F}}_p$. If $(p-1)\nmid n$, choose a primitive root $g$; then $g^n\ne 1$, and $(1-g^n)S=0$ forces $S=0$.

If $(p-1)\mid n$, every nonzero $x$ has $x^n=1$, so $S=p-1\equiv -1(\mathrm{mod}p)$. ThereforeThe source also lists $n=0$, although its premise assumes $n\ge 1$. For that separate case, the integer sum has $p$ terms each equal to one, so it is zero modulo $p$.

The Legendre symbol equal to $1$ says that $a$ is a nonzero square modulo $p$. Choose one root $r\ne 0$. Then $-r$ is another root, distinct because $p$ is odd. Any solution $x$ satisfiesin the field ${\mathbb{F}}_p$, so $x=r$ or $x=-r$. Thus there are

Let $R$ be the sum of the nonzero quadratic residues. Each has two square roots by part (iii), sowhere part (ii) applies because $p>3$ makes $p-1$ not divide $2$. Since $2$ is invertible modulo $p$, $R\equiv 0$.

The sum of all nonzero classes is $p(p-1)/2\equiv 0(\mathrm{mod}p)$. Subtracting $R$ shows that the sum of quadratic nonresidues is also zero. Consequently both requested sums vanish modulo $p$.

Part (ii), with exponent $30$, shows that a prime $q$ fails to divide the sum precisely when $q-1$ divides $30$. The positive divisors are $1,2,3,5,6,10,15,30$. Adding one gives $2,3,4,6,7,11,16,31$, of which the primes areFor these primes the sum is $-1$ modulo $q$; for every other prime it is zero.