<s>[INST] If $p=4k+1$ then $p$ divides $n^2+1$ I am stuck in one step in the proof that if $p$ is congruent to $1 \bmod 4$, then $p\mid (n^2+1)$ for some $n$.
The proof uses Wilson's theorem, $(4k)!\equiv -1 \pmod p$.
The part I am stuck is where it is claimed that $(4k)!\equiv (2k)!^2 \bmod p$. Why is this so?
 [/INST] Take a typical small prime of the form $4k+1$, such as $17$. So $k=4$.
Then
$$16!=\left[(1)(2)(3)(4)(5)(6)(7)(8)\right]\left[(9)(10)(11)(12)(13)(14)(15)(16)\right].\tag{1}$$
We have $16\equiv -1\pmod{17}$, $15\equiv -2\pmod{17}$, $14\equiv -3\pmod{17}$, and so on down to $9\equiv -8\pmod{17}$. 
It follows that $(16)(15)(14)(13)(12)(11)(10)(9)\equiv (-1)(-2)(-3)(-4)(-5)(-6)(-7)(-8)\pmod{17}$.
Our product has an even number of minus signs. It follows that
$$(16)(15)(14)(13)(12)(11)(10)(9)\equiv 8!\pmod{17}.$$
Thus from (1) we find that
$$16!\equiv [8!][8!]=(8!)^2\pmod{17}.$$
The same argument works for any prime of the form $4k+1$. It does not work for a prime of the form $4k+3$, for in that case we get an odd number of minus signs.
</s>