Exercise 3.1.19* ($x^8 \equiv 16 \pmod p$ is always solvable)

Proof. An integer $x$ is a solution of $x^8\equiv 16(\mathit{mod}p)$ if and only if

• If $p=2$, then $x=0$ is a solution.

• If $p\equiv 3(\mathit{mod}4)$, then $-1$ is a quadratic nonresidue modulo $p$.

  • If $2$ is a quadratic residue modulo $p$, then there is some integer $x$ such that $p\mid x^2-2$, so $x$ is a solution.
  • If $2$ is a quadratic nonresidue modulo $p$, then $-2$ is a quadratic residue, because $(-1)$ is a quadratic nonresidue. Thus there is some integer $x$ such that $p\mid x^2+2$, and $x$ is a solution.

• If $p\equiv 1(\mathit{mod}4)$, there are two subcases.

  • if $p\equiv 1(\mathit{mod}8)$, then $\left(\frac{2}{p}\right)=1$, thus $x^2-2\equiv 0(\mathit{mod}p)$ has a solution, which is a solution of $x^8\equiv 16(\mathit{mod}p)$.

  • If $p\equiv 5(\mathit{mod}8)$, then $2$ is a quadratic nonresidue modulo $p$.

    Since $p\equiv 1(\mathit{mod}4)$, $-1$ is a quadratic residue. There is some integer $j$ such that $j^2\equiv -1(\mathit{mod}p)$. Then

    $$x^2+4\equiv (x^2-2j)(x^2+2j)(\mathit{mod}p).$$
    • If $j$ is a quadratic nonresidue modulo $p$, then $2j$ (and $-2j$) are quadratic residues, thus $x^2-2j\equiv 0(\mathit{mod}p)$, has a solution, which also a solution of $x^8\equiv 16(\mathit{mod}p)$.

    • If $j$ is a quadratic residue modulo $p$, then $j\equiv {\omega }^2(\mathit{mod}p)$ for some integer $\omega$, which satisfies

      $${\omega }^4\equiv -1(\mathit{mod}p).$$

      Then $-1$ is a fourth power modulo $p$. By Theorem 2.37,

      $${(-1)}^{\frac{p-1}{4}}=1.$$

      Thus $\frac{p-1}{4}=2k$ for some integer $k$, thus $p=8k+1$. This is impossible, because $p\equiv 5(\mathit{mod}p)$, so this case doesn’t happen. Therefore $j$ is a quadratic nonresidue if $p\equiv 5(\mathit{mod}8)$.

This shows that $x^8\equiv 16(\mathit{mod}p)$ is solvable in all cases. □