<s>[INST] Find all prime $p$ such that $x^2=-1$ has a solution in $\mathbb{Z}/p\mathbb{Z}$ I have found by a numerical experiment that first such primes are: 
$2,5,13,17,29,37,41$. But I cannot work out the general formula for it.
Please share any your ideas on the subject.
 [/INST] The following argument depends on knowing (or separately proving) Wilson's Theorem.
Theorem Let $p$ be prime. Then $(p-1)! \equiv -1 \pmod{p}$.
Now we use Wilson's Theorem to prove the result.  For the sake of concreteness, I will use $p=17$, but the same idea exactly works for all primes congruent to $1$ modulo $4$. All congruences will be modulo $17$, so $17$ will mostly not be mentioned explicitly.
Note that 
$$16!= (1)(2)(3)(4)(5)(6)(7)(8)(16)(15)(14)(13)(12)(11)(10)(9).$$
(Didn't really do anything.)
Note that $16\equiv -1$, $15\equiv -2$, $14\equiv -3$, and so on until $9 \equiv -8$. 
It follows that
$$(15)(14)(13)(12)(11)(10)(9)\equiv (-1)(-2)(-3)(-4)(-5)(-6)(-7)(-8).$$
But the right-hand side is congruent to $(-1)^8(1)(2)(3)(4)(5)(6)(7)(8)$, and of course $(-1)^8=1$.
It follows that $16! \equiv (8!)^2 \pmod{17}$.  But by Wilson's Theorem, $16!\equiv -1 \pmod{17}$, and therefore
$$(8!)^2 \equiv -1 \pmod{17}.$$
We have found an explicit expression for an $x$ such that $x^2\equiv - \pmod{17}$.
If $p \equiv 3 \pmod{4}$, the argument breaks down, because we end up with an odd number of minus signs. (Anyway, the result does not hold when $p\equiv 3\pmod 4$.)
In general, if $p\equiv 1 \pmod 4$, and $q=(p-1)/2$, then
$$(q!)^2 \equiv -1 \pmod{p}.$$
Other primes: It remains to show that the congruence is not solvable if $p \equiv 3\pmod{4}$.  So suppose to the contrary that $b^2\equiv -1\pmod{p}$.  Look at the numbers $b, 2b, 3b, \dots, (p-1)b$.  It is easy to verify they are pairwise incongruent modulo $p$, so their product is congruent to $(p-1)!$ modulo $p$.  Thus
$$b^{p-1}(p-1)! \equiv (p-1)! \pmod p,$$
giving $b^{p-1}\equiv 1 \pmod p$. Let $q=(p-1)/2$.  Then  $b^{p-1} \equiv (-1)^q \pmod p$.  But if $p \equiv 3 \pmod 4$, then $q$ is odd, and we obtain the absurd $-1 \equiv 1 \pmod{p}$. 
</s>