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.
 A: 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}$. 
A: As the ideal $(p)$ is maximal in $\mathbb{Z}.$ The ring $\mathbb{Z}/pZ$ is a field. It follows that the nonzero elements form a group (the group of units $(\mathbb{Z}/p\mathbb{Z})^{\times})$ and this group is cyclic. Note $-1\in(\mathbb{Z}/p\mathbb{Z})^{\times}$ and for $p>2$ the order of $-1$ in this group is 2. As cyclic groups have one and only one subgroup of order $n$ for each positive integer $n$ dividing the order of the group, we observe for $p>2,$ the element $-1$ has a square root if and only if $(\mathbb{Z}/p\mathbb{Z})^{\times}$ contains a subgroup of order $4$ which occurs if and only if $4$ divides $|(\mathbb{Z}/p\mathbb{Z})^{\times}| = p-1,$ i.e. if and only if $p\equiv 1\mod 4.$
Examining case where $p =2,$ trivially reveals that $-1$ has square root.  
A: In a number theory course, you would probably come to the Legendre symbol after a while... http://en.wikipedia.org/wiki/Legendre_symbol 
A: If you know a little group theory it's not too hard. It holds for $p = 2$ so assume $p > 2$. Under multiplication ${\mathbb Z}_p$ is a cyclic group of order $p - 1$. To say an $x$ in ${\mathbb Z}_p$ satisfies $x^2 = -1$ is the same as saying that $x$ is an element of order $4$ in this group. To see why, first note that clearly such an $x$ is of order $4$; $x \neq 1$ and $x^2 = - 1 \neq 1$, while $x^4 = 1$. For the converse, if an element $y$ is of order $4$ then $y^2$ is of order $2$. So $y^4 - 1 = (y^2 - 1)(y^2 + 1) = 0$ in  ${\mathbb Z}_p$. Since $y^2$ is not $1$ it has to be $-1$.
So the question is when does the cyclic group ${\mathbb Z}_p$ have an element of order 4. The orders of the elements of a cyclic group are exactly the divisors of the order. So this happens when $4$ divides $p - 1$ or equivalently when $p = 1 \pmod 4$.
