If $x^n \equiv a \space (31)$, how many values of n and a are there s.t there are only 10 solutions? If $x^n \equiv a \space (31)$, how many values of n and a are there s.t there are only 10 solutions?
I have no idea of how to do this - would really appreciate all help.
 A: We may assume that $a\ne0$, because $x^n \equiv 0 \bmod 31$ has only one solution.
Then, any solution of $x^n \equiv a \bmod 31$ is not zero and so is invertible.
Then, $x_1$ and $x_2$ are solutions of $x^n \equiv a \bmod 31$ iff $x_2=x_1 w$, where $w^n \equiv 1 \bmod 31$.
Therefore, the question reduces to:


*

*For which $n$ does $w^n \equiv 1 \bmod 31$ have exactly $10$ solutions.

*For those $n$, for which $a$ does $x^n \equiv a \bmod 31$ have a solution.
For the first one, $(\mathbb Z/ 31 \mathbb Z)^\times$ is a cyclic group of order $30$ and so has a unique subgroup of order $10$, generated by $g^3$, where $g$ is a primitive root mod $31$. We can take $g=3$.
Thus, $w^n \equiv 1 \bmod 31$ has exactly $10$ solutions iff $\gcd(n,30)=10$, that is, $n \equiv 10$ or $20 \bmod 30$.
The $a$ that are $10$-th powers are exactly $1,g^{10}, g^{20}$, that is, $1,5,25$. 
A: If $a=0$, then the only solution for any $n$ is $x\equiv 0$, so we can assume $a$ is relatively prime to $31$. The multiplicative group modulo $31$ is cyclic, with order $30$, and we can find a generator (i.e., a primitive root); it turns out that $3$ works, so every number $1$ to $30$ can be written as a power of $3$, with exponent unique modulo $30$.
This group is actually a field, so if you want a polynomial to have exactly $k$ solutions, you should look to a degree $k$ polynomial. Tenth powers, modulo $31$, are of the form $3^{10k}$, so we have $3^0\equiv 1$, $3^{10}\equiv 25$, and $3^{20}=5$.
You should also be able to use $n=20$, with the same values for $a$.
