Showing $x^8\equiv 16 \pmod{p}$ is solvable for all primes $p$ I'm still making my way along in Niven's Intro to Number Theory, and the title problem is giving me a little trouble near the end, and I was hoping someone could help get me through it.
Now $x^8\equiv 16\pmod{2}$ is solvable with $x\equiv 0\pmod{2}$, so I assume $p$ is an odd prime. From a theorem earlier in the text, 

If $p$ is a prime and $(a,p)=1$, then the congruence $x^n\equiv a\pmod{p}$ has $(n,p-1)$ solutions or no solution according as $a^{(p-1)/(n,p-1)}\equiv 1\pmod{p}$ or not.

So since $(16,p)=1$, the problem reduces to showing that $16^{(p-1)/(8,p-1)}\equiv 1\pmod{p}$ holds for all $p$. I note that $(8,p-1)$ can only take values $2,4,8$. For $2$, the above equivalence is then $4^{p-1}\equiv 1\pmod{p}$, which is true by Fermat's little Theorem. For $4$, it is then $2^{p-1}\equiv 1\pmod{p}$, which again holds by FlT. However, the case where $(8,p-1)=8$ is throwing me off. At best I see that $16^{(p-1)/8}\equiv 2^{(p-1)/2}\pmod{p}$, but I'm not sure how to show this is congruent to $1$ modulo $p$. Maybe there's a more elegant way to do it without looking at cases. Thanks for any insight.
 A: Hint $\rm \ \ x^8 - 16\ =\ (x^2 - 2)\: (x^2 + 2)\: (x^4 + 4).\,$ If the first two factors have no roots in $\rm\ \mathbb Z/p\ $ then $\:2, -2\:$ are nonsquares thus their product $-4\: $ is a square, so $\rm\: i = \sqrt{-1} \in \mathbb Z/p\:$. Thus the third factor has a root since $\rm\ x^4 + 4\ $ has roots $\rm\: \pm 1\pm i\:$.
A: I usually set this as an exercise when teaching Number Theory.
My hint is to ask the students: what are the solutions of
$z^8=16$ in the complex numbers?
A: For the sake of contradiction, suppose there exists a prime $p$ such that $x^8 \equiv 16 \pmod p$ has no solutions. We can factor
$$x^8 - 16 = (x^2 + 2)(x^2 - 2)(x^2 + 2x + 2)(x^2 - 2x + 2).$$
Since this is not divisible by $p$, we must have
$$\left ( \frac{2}{p} \right ) = \left ( \frac{-2}{p} \right ) = -1 \implies \left ( \frac{-1}{p} \right ) = 1.$$
But then $x^2 - 2x + 2 = (x-1)^2 + 1 \equiv 0 \pmod p$ has a solution, which is a contradiction. 
A: One way is to use the Legendre symbol identity $2^{(p-1)/2} \equiv (\frac{2}{p}) \equiv (-1)^{(p^2-1)/8} \pmod p$ (for odd primes p), keeping in mind that if $(8,p-1)=8$ then $p \equiv 1 \pmod 8$.
A: Another solution, which doesn't need quadratic reciprocity but does use the elementary fact that the product of two quadratic nonresidues is a quadratic residue.
According to $p\bmod 8$,


*

*if $p=1\mod 8$, $\pm 2$ are both quadratic residues

*if $p=3\mod 8$, $-2$ is a quadratic residue but $2$ is not

*if $p=5\mod 8$, $\pm 2$ are not quadratic residues

*if $p=7\mod 8$, $2$ is a quadratic residue but $-2$ is not


If either $2$ or $-2$ is a quadratic residue, $4$ is a 4th power, so $16$ is an 8th power.
This accounts for all primes except those of the form $p=8k+5$, modulo which neither $2$ nor $-2$ is a quadratic residue. The product of two quadratic non-residues is a quadratic residue, so $-1=x^2$ for some $x$.
If $x=y^2$ for some $y$, $y^4=x^2=-1$ so $y^8=1$ so $y$'s order is 8. But the order of any element of a group divides the order of the group, which in this case is $\phi(p)=p-1=8k+4$, and $8\nmid 8k+4$.
So neither $2$ nor $x$ is a quadratic residue, so $2x$ is a quadratic residue $2x=y^2$ for some $y$, so $y^4=(2x)^2=4x^2=-4$ so $y^8=16$.
