Past exam of the short options course of the University of Oxford / 2023 / 1 (Number theory)

The multiplicative group ${\mathbb{F}}_p^{\times }$ is a cyclic group of order $p-1$, so choose a primitive root $g$. Every nonzero residue is uniquely $g^j$, with $j$ taken modulo $p-1$. The condition becomes $(p-1)\mid kj$. Writing $d=\gcd (k,p-1)$, its solutions are $j=0,(p-1)/d,\dots ,(d-1)(p-1)/d$. Zero is not a solution. Therefore the number isThis includes $p=2$. The cyclic group argument gives the exact count, whereas the bound of $k$ roots for a nonzero degree-$k$ polynomial over a field would only give an upper bound.

If $p\mid n$, the field property forces $x=0$, giving exactly one solution. Otherwise, if $x_0$ is any solution, multiplication by $x_0$ is a bijection from the solutions of $z^k=1$ to those of $x^k=n$. Part (i) therefore givesThe two possibilities in the second line distinguish an empty fiber from a coset of the kernel of the power group homomorphism on ${\mathbb{F}}_p^{\times }$.

For $p>3$, quadratic reciprocity givesThe second Legendre symbol is $1$ when $p\equiv 1(\mathrm{mod}3)$ and $-1$ when $p\equiv 2(\mathrm{mod}3)$. Combining it with the sign determined by $p(\mathrm{mod}4)$ shows that a quadratic residue occurs precisely for

For odd $p\ne 5$, quadratic reciprocity has no sign factor because $5\equiv 1(\mathrm{mod}4)$:The nonzero squares modulo $5$ are $1,4$, so the answer for odd primes is $p\equiv 1,4(\mathrm{mod}5)$. The excluded-prime wording also allows $p=2$, where $5\equiv 1$ has a square root. Thus the full answer is

The primes $2,5$ both work, with the zero residue as a solution. For every other prime, multiplicativity of the Legendre symbol and quadratic reciprocity giveThe first factor is positive for $p\equiv 1,7(\mathrm{mod}8)$; the second is positive for $p\equiv 1,4(\mathrm{mod}5)$. They must have the same sign. The Chinese remainder theorem therefore yields

Let $a$ be a root modulo $p^j$. Every lift to a residue modulo $p^{j+1}$ is uniquely $a+t{p}^j$ with $t(\mathrm{mod}p)$. The polynomial expansion givesBecause $a(\mathrm{mod}p)$ is a root and there are no common roots of $f$ and $f^{\prime }$, $f^{\prime }(a)$ is nonzero modulo $p$. Thus precisely one $t$ solvesEvery root at one level therefore has exactly one lift, and every root at the next level reduces to a root at the previous level. Induction proves equality of the counts from $p$ to $p^l$. This is simple-root Hensel lifting by successive residues at finite precision; completeness is unnecessary for this finite-level assertion.

For $f(x)=x^2-n$, a root modulo the odd prime $p$ is nonzero because $p\nmid n$. Its derivative $2x$ is therefore nonzero modulo $p$. Part (i) gives exactly one lift of each root. A nonzero quadratic residue modulo an odd prime has two distinct roots, $x$ and $-x$; a nonresidue has none. Hence