# $p$ prime, $1 \le k \le p-2$ there exists $x \in \mathbb{Z} \ : \ x^k \neq 0,1$ (mod p)

I found this problem in my algebra book, but unfortunately, there is no solution included. Here it is:

Let $p$ be a prime, $1 \le k \le p-2$. Show that there exists $x \in \mathbb{Z} \$ such that $\ x^k \neq 0,1$ (mod $p$).

It looks like a very nice problem, but I have no idea how to solve it.

And a related problem:

Prove that for $k \in \mathbb{N}$:

$\sum _{x \in \mathbb{F}_p ^* }x^k = \begin{cases} 0, \ \ \ \ \ \ \ \ \ \ \ \ p-1 \nmid k\\p-1, \ \ \ \ \ p-1 \ | \ k\end{cases}$

Could you help me?

-
–  lab bhattacharjee May 9 '13 at 8:37

Consider the polynomial $x^k(x^k-1)$. You are asking to show that some $x$ is not a root modulo $p$. That's the same as asking if $x(x^k-1)$ has the same property. But this is a degree $k+1$ polynomial, so it has at most $k+1$ distinct roots. Since $k+1<p$, there is at least one residue mod $p$ that is not a root.

-

For your second question, let $S=1^k+2^k+3^k+\cdots+(p-1)^k$. If $p-1$ divides $k$, then by Fermat's Theorem each of $1^k,2^k,3^k,\dots,(p-1)^k$ is congruent to $1$ modulo $p$, so their sum $S$ is congruent to $p-1$ modulo $p$.

Suppose now that $p-1$ does not divide $k$.

Let $a$ be an integer not divisible by $p$. Then $a,2a,3a,\dots, (p-1)a$ are congruent, in some order, to $1,2,3,\dots,p-1$. So $a^k,(2a)^k, (3a)^k, \dots, ((p-1)a)^k$ are congruent, in some order, to $1^k,2^k,3^k,\dots,(p-1)^k$. Adding up, we find that $$a^k S\equiv S\pmod{p},\quad\text{or equivalently}\quad (a^k-1)S\equiv 0\pmod p.$$ In particular, let $a$ be a primitive root of $p$, that is, an element of order $p-1$ modulo $p$. Since $p-1$ does not divide $k$, it follows that $a^k\not\equiv 1\pmod{p}$, and therefore $a^k-1\not\equiv 0\pmod{p}$. Since $(a^k-1)S\equiv 0\pmod{p}$, it follows that $S\equiv 0\pmod{p}$.

Another way: If $g$ is a primitive root of $p$, then our sum is congruent to $g^k+g^{2k}+g^{3k}+\cdots+g^{(p-1)k}$. The last term is congruent to $1^k$, so it looks a little nicer to write $$S\equiv 1+g^k+g^{2k}+\cdots+g^{(p-2)k}\pmod p.$$ Multiply each side of the above congruence by $1-g^k$, and observe the cancellations. We get $$S(1-g^k)\equiv 1-g^{p-1)k}\pmod{p}.$$ The right-hand side is congruent to $0$ modulo $p$, by Fermat's Theorem. Since $g$ is a primitive root of $p$, and $p-1$ does not divide $k$, it follows that $1-g^k\not\equiv 0\pmod{p}$, and therefore $S\equiv 0\pmod{p}$. Note that essentially we have used the formula for the sum of a finite geometric progression.

-

For the first question,

$x^k\equiv0\pmod p\iff x\equiv 0\pmod p$

Now, we can always find one $x$ (in fact, $p-1$ of them) which is relatively prime to $p$

For $x^k\not\equiv1\pmod p,$ it is sufficient to prove that there is at least one $x$ with order $p-1$ i.e., there is at least one primitive root $\pmod p,$ the proof is available here and here.

-