1
$\begingroup$

The congruence equation, $x^{16} \equiv 256 \pmod p$ for all prime $p$, is solvable. Prove or disprove it.

Here I am thinking of proving that $y^2 \equiv 256 \pmod p$ has solution since the quadratic reciprocity $\Big({256 \over p}\Big) = 1$, but I am not sure if following this path can lead me further.

*Sorry I was meant to determine the solvability of this congruence equation, I edited the question already.

  • 0
    @ShreevatsaR Ah my bad. I didn't read his comment at the bottom.2012-11-12

1 Answers 1

4

For $p=2$ there is an obvious solution.

Note that $256=2^{8}$. So if $2$ is a quadratic residue of $p$, there is an $x$ such that $x^2\equiv 2 \pmod{p}$, and therefore $x^{16}\equiv 256\pmod{p}$. For any prime of the form $p=8k\pm 1$, we have that $2$ is a QR of $p$. Thus our congruence has a solution whenever $p$ is of the form $8k\pm 1$.

For $p$ of the form $8k\pm 3$, we use the following standard result.

Lemma: If $a$ is not divisible by $p$, then $a$ is a $k$-th power residue of $p$ if and only if $a^{(p-1)/d}\equiv 1\pmod{p}$, where $d=\gcd(p-1, k)$.

To apply the Lemma, let $k=16$. Then $\gcd(p-1,k)$ is one of $2$ or $4$. If the $\gcd$ is $4$, we are looking at $256^{(p-1)/4}$. This is $4^{p-1}$. But $4^{p-1}\equiv 1\pmod{p}$ by Fermat's Theorem. The case where $\gcd(p-1,16)=2$ is dealt with similarly.

Thus our congruence has a solution for all primes $p$.