There is solution for $x^{16} \equiv 256 \pmod p$ for all prime $p$. Prove or disprove it. 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.
 A: 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$. 
A: In fact, it's possible to show that there is a solution to $x^8\equiv 16\pmod p$ for all primes $p$. There is nothing to prove for $p=2$ so assume $p$ is odd.
If $p\equiv 1,7\pmod 8$ then it's well known that 2 is a QR modulo $p$, therefore there exists $x$ such that $x^2\equiv 2\pmod p\implies x^8\equiv 16\pmod p$.
If $p\equiv 3\pmod 8$, then it's well known that $\left(\frac{-1}p\right)=\left(\frac2p\right)=-1$, thus $\left(\frac{-2}p\right)=1$, i.e. $-2$ is a QR modulo $p$. Therefore, there exists an $x$ such that $x^2\equiv -2\pmod p\implies x^8\equiv 16\pmod p$.
Finally, if $p\equiv 5\pmod 8$, let $g$ be a generator modulo $p$ and let $y\equiv g^{\frac{p-1}4}\pmod p$. Then $y^2\equiv -1\pmod p$. Also, $\left(\frac yp\right)=-1$ as $y\equiv g^{\frac{p-1}4}\pmod p$ and $\frac{p-1}4$ is odd. Furthermore, we have $\left(\frac2p\right)=-1$. Thus, $\left(\frac{2y}p\right)=1$, so there exists $x$ such that $x^2\equiv 2y\pmod p\implies x^8\equiv 16\cdot y^4\equiv 16\pmod p$.
In all cases, we have found a solution to $x^8\equiv 16\pmod p$, thus $x^{16}\equiv 256\pmod p$ has at least one solution for all $p$.
