4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How would you figure out such an n, and then such an a on top of that? $\endgroup$ – Matthijs Bjornlund Apr 24 '18 at 23:28
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.