a question about congruence

Question

Let $p$ be a prime number such that $p\equiv 1 \pmod8$, $K=\Bbb Z/p\Bbb Z$.

Show that :

$\forall \ c \in K ,\forall \ n \in\mathbb N : x^{2^n}=c$ has at most $2^n$ solution in $K$.

Answer 1

Ok, I'm back. Well, first of all: there are only $\;p\;$ elements in $\;K=\Bbb F_p\;$ , so if $\;2^n>p\;$ the polynomial $\;x^{2^n}-c\;$ cannot have $\;2^n\;$ different solutions in $\;K\;$.

Now, if $\;|K|=p\ge 2^n\;$ there could be a chance, but nor for sure: take for example $\;K=\Bbb F_{17}\;$ , and $\;x^{2^2}-9=x^4-9\in \Bbb F_{17}[x]\;$ , but

$$x^4-9=(x^2-3)(x^2+3)\;,\;\;\text{and neither $\,3\,$ nor $\,-3\,$ is a quadratic residue}\pmod{17}$$

so the polynomial $\;x^4-9\;$ has no roots at all in $\;K=\Bbb Z_{17}\;$ .

In general, for $\;x^8-1\;$ to have eight roots in $\;K\;$ we need that the group of roots of unity of degree eight be a subgroup of $\;K^*:=K\setminus\{0\}\;$ , and this happens iff $\;8\,\mid\,(p-1)\iff p=1\pmod 8\;$ , as given...so yes: the polynomial is reducible to a product of different linear factors in this case.

Answer 2

I don't know if it's the point but using morphism theorems (with $K$ cylcic) we have the fact that :

$\forall n \in \mathbb{N}, \ Card\{c\in K \mid \exists x\in K : x^{2^n}\equiv c \pmod p\}= \frac{p-1}{\gcd(p-1,2^n)}$

If $p>2^n$ we can have $p-1=2^lp_1^{a_1}...p_i^{a_i}>2^n$ with $l\ge 3, a_j\ge 1$ or $p-1<2^n$ or we can have $p-1=2^n$. In the third case we just have one $2^n$-th power. In the other cases we will have the fact that $2^{\min(l,n)}<2^n$ and $2^{\min(l,n)}<2^l$, so the number of $2^n$-th powers will be $2^{l-\min(l,n)}p_1^{a_1}...p_i^{a_i}$.

If $p<2^n$ we just have the form $p-1=2^lp_1^{a_1}...p_i^{a_i}<2^n$ with $l\ge 3, a_j\ge 1$. Then we will have $2^l<2^n$, so the number of $2^n$-th powers will be $p_1^{a_1}...p_i^{a_i}$.