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

This is easiest to approach with an example first.

• For instance, take \(p=11\).
• Then \[10!=1(2)(3)(4)(5)(6)(7)(8)(9)(10)=(2\cdot 4\cdot 6\cdot 8\cdot 10)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)\] \[=2^5 (1\cdot 2\cdot 3\cdot 4\cdot 5)\cdot (1\cdot 3\cdot 5\cdot 7\cdot 9)\, .\]
• 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\) - exactly the missing pieces to \(10!\).
• So I factor out \(-1\) from those three, thus: \[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)\] \[\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)!\]
• Now cancel \(10!\) from both sides, and we get \[1\equiv 2^5 (-1)^3\, ,\] which means \[2^{(11-1)/2}\equiv 2^5\equiv (-1)^3\equiv -1\] 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 \[\left(\frac{p-1}{2}-1\right)\frac{1}{2}+1=\frac{p+1}{4}\] 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 \[\left(\frac{p-1}{2}\right)\frac{1}{2}=\frac{p-1}{4}\] 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