We will try to show this by writing \((p-1)!\) in two different ways.

This is easiest to approach with an example first. We'll indicate different ideas to pay attention to with bullets.

• For instance, take \(p=11\). Then we can write \begin{equation*}10!=1(2)(3)(4)(5)(6)(7)(8)(9)(10)\end{equation*} \begin{equation*}=(2\cdot 4\cdot 6\cdot 8\cdot 10)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)\end{equation*} \begin{equation*}=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)\, .\end{equation*} Notice that \(1,3,5\) repeat; these are all the odd numbers less than or equal to \(\frac{11-1}{2}=5\).

• Now we will try to create \(10!\) again from what is left. The only ones we need to change would be \(1,3,5\), as I just said.

• But \(-1,-3,-5\equiv 10,8,6\), which are exactly the missing pieces to \(10!\). So I factor out \(-1\) from those three, thus: \begin{equation*}10!=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (-1)^3\cdot (-1\cdot -3\cdot -5)\cdot (7\cdot 9)\end{equation*} \begin{equation*}\equiv 2^5 (-1)^3 (1\cdot 2\cdot 3\cdot 4\cdot 5)(10\cdot 8\cdot 6)(7\cdot 9)\equiv (-1)^3 2^5 (10)!\end{equation*}

• Finally, cancel \(10!\) from both sides, and we get \begin{equation*}1\equiv 2^5 (-1)^3 \Longrightarrow 2^{(11-1)/2}\equiv 2^5\equiv (-1)^3\equiv -1\end{equation*} and so 2 is not a QR of 11.

Proving the general case basically follows this to its natural conclusion; there was nothing special in the above argument about \(p=11\).

After writing \((p-1)!\) and factoring out \(2^{(p-1)/2}\), the “repeated” numbers will be the odd numbers between 1 and \((p-1)/2\). Clearly the only “missing” numbers are even ones between \((p-1)/2\) and \(p\), which are just the negatives of these odd numbers, so the same argument as above with \((p-1)!\) will work.

• If \(p\equiv 3\) (mod \(4\)), like \(p=11\), then \((p-1)/2\) is odd so there will be \begin{equation*}\left(\frac{p-1}{2}-1\right)\frac{1}{2}+1=\frac{p+1}{4}\end{equation*} repeated factors, as \(1,3,5\) above.

• If \(p\equiv 1\) (mod \(4\)) (like \(p=13\)), on the other hand, then \((p-1)/2\) is even and there are exactly \begin{equation*}\left(\frac{p-1}{2}\right)\frac{1}{2}=\frac{p-1}{4}\end{equation*} repeated factors (in that case, still \(1,3,5\)).

In either case, whether the number of repeated factors (\((p+1)/4\) or \((p-1)/4\), respectively) is even or odd determines whether 2 is a quadratic residue!

So in general:

• If \(p\equiv 1\) (mod \(4\)) and \(\frac{p-1}{4}\) is even, it works, so \(p\equiv 1\) (mod \(8\)) does have 2 as a QR.

• If \(p\equiv 1\) (mod \(4\)) and \(\frac{p-1}{4}\) is odd, it does not work, so \(p\equiv 5\) (mod \(8\)) does not have 2 as a QR.

• If \(p\equiv 3\) (mod \(4\)) and \(\frac{p+1}{4}\) is even, it works, so \(p\equiv 7\) (mod \(8\)) does have 2 as a QR.

• If \(p\equiv 3\) (mod \(4\)) and \(\frac{p+1}{4}\) is odd, it does not work, so \(p\equiv 3\) (mod \(8\)) does not have 2 as a QR.