Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
2  
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

4 Answers 4

up vote 15 down vote accepted

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

share|improve this answer
    
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}$.

share|improve this answer
    
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.

share|improve this answer
    
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

share|improve this answer
    
it's interesting. Thank you for pointing that. –  Sergey Jun 28 '11 at 16:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.