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.

-
You need to select all primes that are not equal to 3 (modulus 4). See also oeis.org/A002313 – Listing Jun 28 '11 at 15:33
These are precisely the primes that are 1 mod 4 (and also 2); see e.g. Fermat's theorem on sums of two squares. Maybe someone else can post a more illuminating answer. (You don't need the full theorem.) – ShreevatsaR Jun 28 '11 at 15:34
By $\mathbb{Z}_p$, do you mean integers modulo $p$ or $p$-adic integers ? Solving the equation in the former is possible if and only if $p = 2$ or $p \equiv 1 \mod 4$, Solving the equation in the latter requires a solution mod $p$ and the lifting principle known as Hensel's Lemma. – Joel Cohen Jun 28 '11 at 15:46
@Joel: you mean 1, not -1. – Chris Eagle Jun 28 '11 at 15:48
@ Chris : Sure, Thanks for pointing that out :) – Joel Cohen Jun 28 '11 at 15:49

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

-
thank you, your answer is very clear. – Sergey Jun 28 '11 at 16:34
And the fact that the group is cyclic implies that there is an element of order $4$, if $p = 1 \mod 4$. – Aryabhata Jun 29 '11 at 18:30

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

-
This is nice and explicit (+1), but how do you prove that $p \equiv 3 \pmod 4$ never has $-1$ as a square? – ShreevatsaR Jun 28 '11 at 19:34
@ShreevatsaR: Started writing out a quickie version, again based marrying Wilson's Theorem with a streamlined version of the Euler Criterion. Would have been easy, it is in a book I co-wrote. But it doesn't have the fun factor of the $q!$ answer. Maybe for completeness will tack it on tomorrow. – André Nicolas Jun 28 '11 at 19:47
No, nevermind. :-) This is a good answer as it is. – ShreevatsaR Jun 28 '11 at 20:33
thank you for useful reply. Wilson's theorem is used further in my exercise list. – Sergey Jun 29 '11 at 6:27

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.

-
there is a simiral answer from Zarrax. But your answer deals with commutative algebra in somewhat higher level than Zarrax's answer. Thank you for providing higher level of abstraction on the matter. – Sergey Jun 28 '11 at 16:39

In a number theory course, you would probably come to the Legendre symbol after a while... http://en.wikipedia.org/wiki/Legendre_symbol

-
it's interesting. Thank you for pointing that. – Sergey Jun 28 '11 at 16:15