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?

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$.
