An intermediate Arithmetic exercise

Question

Deduce that if $p$ is a prime number of the form $(4k + 1)$ for $(k ∈N),$
then there exists $a ∈ N$ such that $(a² + 1)$ is a multiple of $p$.  

Answer 1

Look at the product $$ 1 \times 2 \times \ldots \frac{(p-1)}{2}\frac{(p+1)}{2} \times \ldots \times (p-1)$$

Notice that $$ \frac{(p+1)}{2} \cong -\frac{(p-1)}{2} \pmod p, $$ and so on.

On one hand, this product equals $ (p-1)!$ which is $-1 \pmod p$, while on the other hand, it equals $$[\frac{p-1}{2}!]^2.$$ So you have a $x$ such that $x^2 +1 $ is divisible by $p$.