Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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