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?
 A: 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.
A: You group $\{1,p-1\},\{2,p-2\},...,\{2k,2k+1\}$ together, and the product of the first terms are equal to to product of second terms as there are even number of terms.
A: This problem is trivial with Legendre's symbol:$\left(\frac{-1}{p}\right)=1$ for every prime number $p\equiv 1\pmod{4}$.But of course,without knowing advanced methods like that it gets harder to solve this problem.Here is another solution:
Lemma: Let $p\equiv 1\pmod{4}$ be a prime number.Prove that $\prod_{k=1}^{p-1}(k^2+1)\equiv 0\pmod{p}$.
Sketch of solution: We have $\prod_{k=1}^{p-1}(k^2+1)=\prod_{k=1}^{p-1}(k+i)\cdot\prod_{k=1}^{p-1}(k-i)$.
The main idea is to observe that $$\prod_{k=1}^{p-1}(k+i)=i^{p-1}-1+pQ(i)$$ and $$\prod_{k=1}^{p-1}(k-i)=(-i)^{p-1}-1+pQ(-i)$$ for some polynomial $Q$.
From here it follows that $\prod_{k=1}^{p-1}(k^2+1)\equiv (i^{p-1}-1)[(-i)^{p-1}-1]\equiv 0\pmod{p}$
From the above lemma it follows that there exists $k\in\{1,2,...,p-1\}$ such that $p|k^2+1$.
