$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?
 A: 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.
A: 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. 
A: 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.
