Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / C / C2

A primitive root modulo $p$ is a generator of the cyclic multiplicative group $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, so it has order $p-1$. If $g$ is one generator, the generators are exactly $g^k$ with $\gcd (k,p-1)=1$. Hence there are $\boxed{\varphi (p-1)}$. For $p=2$ the group is trivial and its unique element is its generator, consistently with $\varphi (1)=1$.

For $n\ge 1$, the zero residue contributes zero. Multiplication by any nonzero $\alpha$ permutes the nonzero residues, so the sum $S$ satisfies $S={\alpha }^{n}S$ in ${\mathbb{F}}_p$. If $p-1\nmid n$, choose a primitive root $\alpha$; then ${\alpha }^n\ne 1$, forcing $S=0$. If $p-1\mid n$, every nonzero term equals one, so $S=p-1=-1$ in the field.

The printed display also mentions $n=0$, although its introductory assumption is $n\ge 1$. For that extra case the sum of the $p$ integer values $x^0$ for $1\le x\le p$ is $p\equiv 0$, so that branch is consistent too. The result is

The Legendre symbol being one means $a$ is nonzero and a square modulo $p$. Take one root $r\ne 0$. Factoring $x^2-r^2=(x-r)(x+r)$ in the field shows that any root is $r$ or $-r$. Since $p$ is odd these are distinct. Thus there are exactly $\boxed{2}$ solutions.

Each nonzero quadratic residue is attained twice as $x^2$ for $1\le x\le p-1$. Therefore twice the sum of those residues is ${\sum }_{x=1}^{p-1}{x}^2$, which is zero modulo $p$ by (ii), since $p-1>2$. As two is invertible modulo $p$, the sum of the residues is zero. The sum of all nonzero residues is $p(p-1)/2\equiv 0$, so subtracting gives the same result for the nonresidues. Hence $\boxed{\text{both indicated sums are }0(\mathrm{mod}p)}$.

By (ii), failure of divisibility is equivalent to $q-1\mid 30$. The positive divisors of $30$ are $1,2,3,5,6,10,15,30$; adding one gives $2,3,4,6,7,11,16,31$. Retaining only primes yields