Find all $p$ primes such that $-8$ is quadratic residue modulo $p$ I need help with finding all $p$ primes such that $-8$ is quadratic residue modulo $p$.
I know that :
$(\frac{-8}{p})=(\frac{-1}{p})(\frac{8}{p})=(\frac{-1}{p})(\frac{2^2}{p})(\frac{2}{p})=(\frac{-1}{p})(\frac{2}{p})=(-1)^{\frac{p-1}{2}}
(-1)^{\frac{p^2-1}{8}}$
But I'm not sure how to continue, I wanted to use CRT but 4 and 8 are not coprime....
How can I continue from here?
 A: Hint 1: Show that $(-1/p) = 1$ if and only if $p \equiv 1 \pmod{4}$ (consider using Euler's Criterion).
Hint 2: Show that for $p \equiv 1 \pmod{4}$, $2^{(p - 1)/2} \equiv (-1)^{(p - 1)/4} \pmod{p}$, and thus $(2/p) \equiv (-1)^{(p - 1)/4} \pmod{p}$ by Euler's Criterion. Similarly, for $p \equiv 3 \pmod{4}$, show that $2^{(p - 1)/2} \equiv (-1)^{(p + 1)/4} \pmod{p}$, and thus $(2/p) \equiv (-1)^{(p + 1)/4} \pmod{p}$. One way to do this is start with $2^{(p - 1)/2} \left(\frac{p - 1}{2} \right)!$ on one side of an equivalence modulo $p$, expand the factorial term by term, and show that the other side evaluates to $(-1)^{(p - 1)/4} \left(\frac{p - 1}{2} \right)!$ and $(-1)^{(p + 1)/4} \left(\frac{p - 1}{2} \right)!$ for $p \equiv 1 \pmod{4}$ and $p \equiv 3 \pmod{4}$, respectively. (Gauss's Lemma is also possible for this part).
Hint 3: If you complete both the above steps, you will have classifications of primes $p$ for which $-1$ and $2$ are quadratic residues or nonresidues modulo $p$. This gives you a classification of $p$ where $-8$ is a quadratic residue, since as per your equation, we consider the case where $(-8/p) = (-1/p)(2/p) = 1$, or $(-1/p) = (2/p) = \pm 1$.
Also: if the moduli in a system of congruences are not relatively prime, only consider the cases where the congruences are consistent with each other. For example, if we have the system $x \equiv 1 \pmod{4}$ and $x \equiv 5 \pmod{8}$, the second congruence is a stronger version of the first (since $x = 8k + 5 = 4(2k + 1) + 1 \equiv 1 \pmod{4}$). On the other hand, the system $x \equiv 1 \pmod{4}$ and $x \equiv 3 \pmod{8}$ is inconsistent and not possible.
