How quickly can we detect if $\sqrt{(-1)}$ exists modulo a prime $p$?

Question

How quickly can we detect if $\sqrt{(-1)}$ exists modulo a prime $p$? In other words, how quickly can we determine if a natural, $n$ exists where $n^2 \equiv -1 \bmod p$?

NOTE

This $n$ is essentially the imaginary unit modulo $p$.

Answer 1

If $p = 2$ then $-1$ is a square mod $p$, so we may now assume that $p$ is odd. Suppose that $n^2 \equiv -1 \bmod p$ for some $n \in \mathbb{N}$. Then, using that $\mathbb{Z}/p\mathbb{Z}$ is a field, $$ 1 \equiv n^{p-1} \equiv (n^2)^{\frac{p-1}{2}} \equiv (-1)^{\frac{p - 1}{2}} \bmod p $$ which implies that $\frac{p-1}{2}$ is even, thus, that $p \equiv 1 \bmod 4$. Conversely, suppose that $p \equiv 1 \bmod 4$. Then $\frac{p-1}{2}$ is even. Using that $\mathbb{Z}/p\mathbb{Z}$ is a field, pick a generator $x$ of $\mathbb{Z}/p\mathbb{Z}^\times$. $x^{\frac{p-1}{2}}$ is a root of $T^2 - 1$ different from $1$, such that $$ -1 \equiv x^{\frac{p-1}{2}} \equiv (x^{\frac{p-1}{4}})^2. $$ We have shown that $-1$ is a square mod $p$ if and only if $p \equiv 1 \bmod 4$ or $p = 2$.

As a sidenote, this observation can be generalised to $\mathbb{Z}/p^n\mathbb{Z}$ for a prime $p$, i.e. $-1$ is a square mod $p^n$ if and only if $p \equiv 1 \bmod 4$ (or $p = 2$ AND $n = 1$). Using the Chinese Remainder Theorem then, one can easily conclude that $-1$ is a square modulo $n$ if and only if $n$ is divisible by $2$ at most once and all odd primes $p$ dividing $n$ satisfy $p \equiv 1 \bmod 4$.

Answer 2

For $p>2$ prime, $-1$ is a quadratic residue modulo $p$ if and only if $p \equiv 1 \bmod 4$. So you can determine whether $-1$ is a quadratic residue modulo $p$ as quickly as you can find the remainder of $p$ upon division by $4$.

Answer 3

Let's do some experimentation.

$p = 3$: no.

$p = 5$: yes, $2^2 \equiv -1$.

$p = 7$: no.

$p = 11$: no.

$p = 13$: yes, $5^2 \equiv -1$.

$p = 17$: yes, $4^2 \equiv -1$.

$p = 19$: no.

$p = 23$: no.

It appears that only those prime numbers which are congruent to $1$ modulo $4$ have this property.