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.

  • $\begingroup$ This problem naturally splits into cases. Don't be afraid to think casewise. $\endgroup$ – Qiaochu Yuan Oct 14 '10 at 9:56
  • 2
    $\begingroup$ This problem played a role in the development of the Grunwald–Wang theorem; see en.wikipedia.org/wiki/Grunwald-Wang_theorem#History $\endgroup$ – 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$.

  • $\begingroup$ 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$? $\endgroup$ – yunone Oct 14 '10 at 10:13
  • $\begingroup$ Yep that's right (unless if a=0 (mod p)). $\endgroup$ – 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\:$.

  • $\begingroup$ 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$? $\endgroup$ – yunone Oct 14 '10 at 23:27
  • 1
    $\begingroup$ 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$ $\endgroup$ – Bill Dubuque Oct 14 '10 at 23:31
  • $\begingroup$ 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$. $\endgroup$ – 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?


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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.