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.

  • $\begingroup$ Can you not take x=1, p=2? $\endgroup$ – Alex J Best Nov 12 '12 at 5:00
  • $\begingroup$ "FOR ALL" prime $p$ $\endgroup$ – fmat Nov 12 '12 at 5:10
  • $\begingroup$ @yunone True... but Alex J Best's example isn't a counterexample in this case. $\endgroup$ – roliu Nov 12 '12 at 7:54
  • $\begingroup$ @ShreevatsaR Ah my bad. I didn't read his comment at the bottom. $\endgroup$ – roliu Nov 12 '12 at 8:13

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


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.