Past exam of the mathematics course of the University of Cambridge / 2008 / ia / Paper 4 / 6D / b / Solution

Take a generator $u$ of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, which has order $p-1$. Write $x=u^a$. Since any possible nonzero base is $y=u^r$, the condition of being a $k$th power isBy part (a), this linear congruence is soluble exactly when $d=\gcd (k,p-1)$ divides $a$. MeanwhileThus the required test isThe exponent residue classes divisible by $d$ are $0,d,\dots ,p-1-d$, so there are exactly $(p-1)/d$ distinct nonzero $k$th powers. Equivalently, part (a) shows each value has exactly $d$ preimages under the power map.