# When is $2$ a quadratic residue mod $p$?

For which prime numbers $$p$$ is $$2$$ a quadratic residue modulo $$p$$.

I know that $$2$$ is a quadratic residue iff $$2^{\frac{p-1}{2}} =1 \; \bmod \;(p)$$ so $$2^{p-1} =1 \; \mod \; (p).$$ But I don't know what to do.

• $2$ is a QR of the odd prime $p$ if and only if $p\equiv \pm 1\pmod{8}$. Proofs take a while. The most common one involves manipulation of factorials. – André Nicolas May 9 '15 at 21:38
• See also this blog post which refers to this answer. – Martin Sleziak Dec 2 '16 at 12:20

Let $s = \frac{p-1}{2}$, and consider the $s$ equations

\begin{align} 1&= (-1)(-1) \\ 2&=2(-1)^2 \\ 3&= (-3)(-1)^3 \\ 4&= 4 (-1)^4 \\ & \quad\quad \ldots\\ s&= (\pm s)(-1)^s \end{align}

Where the sign is always chosen to have the correct resulting sign.

Now multiply the $s$ equations together. Clearly on the left we have $s!$. On the right, we have a $2,4,6,\dots$ and some negative odd numbers. But note that $2(s) \equiv -1 \mod p$, $2(s-1) \equiv - 3 \mod p$, and so on, so that the negative numbers are the rest of the even numbers mod $p$, but disguised. So the right side contains $s! (2^s)$ (where we intuit this to mean that one two goes to each of the terms of the factorial, to represent the even numbers $\mod p$).

We only have consideration of $(-1)^{1 + 2 + \ldots + s} = (-1)^{s(s+1)/2}$ left.

Putting this all together, we get that $2^s s! \equiv s! (-1)^{s(s+1)/2} \mod p$, or upon cancelling factorials that $2^s \equiv (-1)^{s(s+1)/2}$. And $s(s+1)/2 = (p^2 - 1)/8$, so we really have $2^{(p-1)/2} \equiv (-1)^{(p^2 - 1)/8}$.

So it depends on $p \pmod 8$. [This is probably the involved manipulation of factorial proof that André alludes to].

The second supplementary law of quadratic reciprocity says that: $$\biggl(\frac{2}p\biggr)=\bigl(-1\bigr)^{\tfrac{p^2-1}8}$$ Namely, $2$ is a square modulo $p$ if and only if $p\equiv\pm 1\mod 8$.

The other method is based on roots of unity $$\sqrt{2}e^{2i \pi /8}= 1+i$$ For $$p$$ odd $$(\sqrt{2}e^{2i \pi /8})^p = \sqrt{2} 2^{(p-1)/2}e^{2i \pi /8} (e^{2i \pi /8})^{p-1}=(1+i)(\frac{2}{p})i^{(p-1)/2}$$

$$(1+i)^p \equiv 1^p+i^p \equiv 1+i (-1)^{(p-1)/2}\equiv (1+i) i^{(p-1)/2} (-1)^{(p^2-1)/8} \bmod p$$ Thus $$(\frac{2}{p}) \equiv (-1)^{(p^2-1)/8} \bmod p$$