I have to prove that $x^{16}-16\equiv 0 \mod p$ has a solution for every prime $p$. I already know (from a previous work) that $x^8-16\equiv 0 \mod p$ has a solution for every prime.
In my opinion, I have nothing to show anymore, because $x^{16}-16=(x^2)^8 - 16 \equiv 0 \mod p$, so I know for each $p$ there is a integer $x^2$ such that this equation holds.
What's wrong about my thoughts?
The statement seems incorrect. $x^{16}-16\equiv0\pmod p$ obviously doesn't have a solution for $p=17$, by Fermat's little theorem. It also doesn't have a solution for $p=97$.
While one can prove that $x^{16}-16\equiv0\pmod p$ has a solution for every $p\not\equiv1\pmod{16}$, it seems that it only has a solution for half the primes $p\equiv1\pmod{16}$. (For these primes, having a solution is equivalent to $z$ being a quadratic residue, where $z^2\equiv2\pmod p$. This seems to happen half the time, as a random model would predict.)