Numbers $m$ such that $\sqrt{-1}$ mod $m$ exists

Question

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]

Answer 1

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

Answer 2

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$