Numbers $m$ such that $\sqrt{-1}$ mod $m$ exists Question: For which number $m$ the following equation has a solution? $$n^2 \equiv -1 \mod m $$ 
Remark: The code below provides the first such numbers: $1,2,5,10,13,17$.
By searching this sequence on OEIS, we find the expected numbers: A008784 (we took its title).
This link contains the following statement:  

Numbers whose prime divisors are all congruent to 1 mod 4, with the
  exception of at most a single factor of 2. - Franklin T.
  Adams-Watters, Sep 07 2008

Then, the question reduces to prove the above statement. 

sage: for m in range(20):
....:     for n in range(m):
....:         if (n**2+1).mod(m)==0:
....:             print([m])
....:
[1]
[2]
[5]
[5]
[10]
[10]
[13]
[13]
[17]
[17]

 A: Theorem: The equation $$n^2 \equiv -1 \mod m$$ has a solution if and only if $$ m = 2^{\epsilon} \prod_{i=1}^s p_i^{r_i},$$ with $\epsilon \in \{0,1\}$ and prime $p_i \equiv 1 \mod 4$.
Proof:  First of all, if $4$ divides $m$ then $n^2 \equiv -1 \mod 4$, which is not possible. So $v_2(m) \in \{0,1\}$.  
Now, if $m$ has a prime factor $p$ of the form $4k+3$. By Euler's criterion we have:
$$ n^2 \equiv -1 \mod p \  \  \Rightarrow  \ \ (-1)^{\frac{p-1}{2}} \equiv 1 \mod p.$$
But $\frac{p-1}{2} = 2k+1$, so $-1 = (-1)^{\frac{p-1}{2}} \equiv 1 \mod p$, contradiction with $p$ odd.     
It follows that $m$ must be of the form $2^{\epsilon} \prod_{i=1}^s p_i^{r_i}$, with $\epsilon \in \{0,1\}$ and prime $p_i \equiv 1 \mod 4$.  
It remains to show that the equation has a solution for every such $m$. Obviously, $m=2$ is ok, and by the Chinese remainder theorem, we can assume that $m=p^r$ with prime $p \equiv 1 \mod 4$.    
Let $G$ be the group $(\mathbb{Z}/m\mathbb{Z})^{\times}$, it is cyclic:  $G \simeq C_{\varphi(m)}$ with $\varphi(m)=p^{r-1}(p-1)$.    
Recall that:

A finite group $G$ is cyclic iff for every divisor $d$ of $|G|$ there
  is a unique subgroup of order $d$.

Now, by assumption, $4$ divides $\varphi(m)$, so $G$ has a (unique) subgroup $C_4$. Let $H:= \{g^2 | g \in C_4 \}$. Then $H$ must be the unique subgroup $C_2$, so it must be $\{-1,1\}$.
Conclusion, there is $g \in C_4 \subset G \subset \mathbb{Z}/m\mathbb{Z}$ with $g^2 = -1$, and the result follows. $\square$
A: Worth emphasis is that the result presented in Sebastion's answer is in fact a special case of the following generalized Euler's Criterion.
Theorem $\ $ Let $\ a,\,n\,$ be integers, with $\,a\,$ coprime to $\,n\ =\ 2^e \,p_1^{e_1}\cdots p_k^{e_k}\,,\ \ p_i\,$ primes.
$\qquad\qquad\quad x^2\equiv  a \pmod{\!n}\,\ $ is solvable for $\,x\,$ 
$\quad\  \iff\ \ \, a^{\large (p_i - 1)/2} \equiv 1 \pmod{\!p_i}\quad $  for all $\ i\le k$
$\qquad\qquad\ \ \ $ and $\ \ e>1 \,\Rightarrow\, a\equiv 1\pmod{\! 2^{2+\delta}},\ \ \ \delta = 1\ \ {\rm if}\ \ e\ge 3\ \ {\rm else}\ \ \delta = 0$ 
Proof: See e.g. Ireland and Rosen,  A Classical Introduction to Modern Number Theory, Proposition 5.1.1 p.50.  
The above criterion is practical if one knows a full factorization of $\,n,\,$ since the exponentiations may be quickly computed by repeated squaring.  
Beware that the criterion cannot be expressed equivalently as a simple Jacobi symbol calculation. For example we have $(8|15) = 1\ $ but $\,8\,$ is not a square $\,\rm (mod\ 15)$.
