# 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.

-
This problem naturally splits into cases. Don't be afraid to think casewise. – Qiaochu Yuan Oct 14 '10 at 9:56
This problem played a role in the development of the Grunwald–Wang theorem; see en.wikipedia.org/wiki/Grunwald-Wang_theorem#History – lhf Oct 17 '10 at 23:46

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$.

-
Thanks, I overlooked that identity. I had a small question to add. I know if $a$ is a quadratic residue modulo $p$, then the Legendre symbol $(a|p)=1$ . However, if by some calculation I find that $(a|p)=1$, is it also the case that $a$ is a quadratic residue modulo $p$? – yunone Oct 14 '10 at 10:13
Yep that's right (unless if a=0 (mod p)). – Douglas S. Stones Oct 14 '10 at 21:22

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 so 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\:$.

-
I'm only learning elementary number theory, so I'm not too familiar with this. Could you please explain how $-4$ being a square implies $i=\sqrt{-1}\in\mathbb{Z}/p$? – yunone Oct 14 '10 at 23:27
If $j^2 \equiv -4$ then $(j/2)^2 \equiv -1$. Note: since p is odd, $1/2 \in \mathbb Z/p$, in fact $1/2 \equiv (p+1)/2$ – Bill Dubuque Oct 14 '10 at 23:31
The quartic factors even further: $x^8 - 16 = (x^2+2)(x^2-2)(x^2+2x+2)(x^2-2x+2)$. The last two factors both have discriminant $-4$, so if neither 2 nor $-2$ is a square mod $p$ then $-1$ is and thus the last two factors both have roots mod $p$. – KCd Oct 11 '11 at 2:35

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?

-