If $x^n \equiv a \space (31)$, how many values of n and a are there s.t there are only 10 solutions?

Question

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.

Answer 1

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$.

Answer 2

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$.