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 came across this problem and I believe Lagrange's theorem is the key to its solution. The question is:

Let $p$ be an odd prime. Prove that there is some integer $x$ such that $x^2 \equiv −1 \pmod p$ if and only if $p \equiv 1 \pmod 4$.

I appreciate any help. Thanks.

share|improve this question
    
If you mean Lagrange's four-square theorem, then it is probably overkill if it works at all. See Fermat's theorem on sums of two squares‌​. which points to several proofs. –  lhf Mar 19 '12 at 12:14
    
Read up on the Legendre Symbol, which uses Euler's criterion, which can be proved with Lagrange's Theorem. –  davin Mar 19 '12 at 12:17
    
@ lhf I meant Lagrange's theorem in group theory. en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory) –  Mike Mar 19 '12 at 12:17
    
For the simpler theorem (which is equivalent to the sum of two squares theorem), you can use Wilson's theorem. –  lhf Mar 19 '12 at 12:19

6 Answers 6

If such an element exists it would have order $4$, so by Lagrange's theorem $4|p-1$ and thus $p\equiv 1\mod 4$.

If $p\equiv 1\mod 4$ we can use Wilson's theorem to explicitly write down an element that squares to $-1$: $$ -1\equiv(p-1)!\equiv 1\cdot\ldots\cdot \frac{p-1}{2}\frac{p+1}{2}\cdot\ldots\cdot(p-1)\equiv\left(\left(\frac{p-1}{2}\right)!\right)^2\cdot(-1)^{\frac{p-1}{2}}\equiv\left(\left(\frac{p-1}{2}\right)!\right)^2 $$

share|improve this answer
6  
Lagrange's theorem here is quite nice but is a bit of an overkill: $1\equiv x^{p-1} \equiv (x^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2}$ implies $(p-1)/2$ even. –  lhf Mar 19 '12 at 12:29
    
@lhf: You're right! The OP wanted to use Lagrange, so I guess it will be useful for him to see how to apply it here. –  Michalis Mar 19 '12 at 12:35
    
Sure, well done. –  lhf Mar 19 '12 at 12:40
    
I'm a bit unsure how to show that if the element exists it is of order 4. Maybe its just because its early, but I just do not see at the moment. –  Mike Mar 19 '12 at 12:52
    
@Mike: Please see lhf's comment for a slightly easier argument of why $p\equiv 1\mod 4$ if $-1$ is a square. What I meant is the following: The order of an element $a\in\mathbb{Z}/p\mathbb{Z}^*$ is defined as the smallest integer $n$ such that $a^n\equiv 1 \mod p$. If $a^2\equiv -1$ then $a^4\equiv 1$, so the order of $a$ is 4. This also means that the subgroup of $\mathbb{Z}/p\mathbb{Z}^*$ generated by $a$ has $4$ elements. By Lagrange's theorem $4$ must divide the size of $\mathbb{Z}/p\mathbb{Z}^*$, which is $p-1$ –  Michalis Mar 19 '12 at 13:33

There is a slightly more general version of this result: if a finite field has an odd number $q$ of elements, then the equation $x^2+1=0$ has a solution in the field if and only if $q\equiv1\pmod4$. In your case you can of course take $\mathbb Z/p\mathbb Z$ as finite field, in which case $q=p$.

Here's a simple proof. Group all nonzero elements of your field in packets $\{a,-a,a^{-1},-a^{-1}\}$. It is easy to see that if one would have generated the packet from any of its three elements other than $a$, it would still give the same packet. In other words one has partitioned the $q-1$ nonzero elements into packets. Not all packets have four distinct elements though: while it cannot happen that $a=-a$ (since $q$ is odd), it can happen either that $a=a^{-1}$ or that $a=-a^{-1}$; in both cases the packet has two elements instead of four.

Now $a=a^{-1}$ happens if and only if $a^2=1$, and since $a^2-1=(a-1)(a+1)$, this occurs precisely for $a=1$ and $a=-1$, giving one packet of this type, regardless of the field. For the other type $a=-a^{-1}$, this happens if and only if $a^2=-1$. That need not occur at all, but if it does, there are precisely two solutions to this quadratic equation, which then together define a single packet of this second type. Now since all remaining packets are of size $4$, and all packet sizes add up to $q-1$, one easily sees that a packet of the second type exists if and only if $q-1$ is a multiple of $4$.

share|improve this answer
    
+1, very nice proof! –  lhf Mar 19 '12 at 13:27

Hint: When $p$ is prime: $-1 \equiv (p-1)!\pmod p$ and when $p\equiv 1\pmod 4$, $(p-1)!\equiv (\frac{p-1}{2})!^2\pmod p$

Alternatively, you can use the fact that a polynomial of degree $n$ has at most $n$ roots, modulo $p$, and that $x^{p-1}-1 = (x^{\frac{p-1}2}-1)(x^{\frac{p-1}2}+1)$ is known to have $p-1$ roots, modulo $p$, so $x^{\frac{p-1}2}+1$ must have a root, $r$, and then $r^{\frac{p-1}4}$ has the property that $r^2\equiv -1\pmod p$

share|improve this answer

An alternative to the other (perfectly good) proofs already suggested is the following. We use that the group $\mathbb{Z}_p^*$ of units of the ring $\mathbb{Z}_p$ is cyclic of order $p-1$, and consider its generator $a$. Then as $(a^{\frac{p-1}{2}})^2=1$, and $\mathbb{Z}_p$ is an integral domain, either $a^{\frac{p-1}{2}}=1$ or $a^{\frac{p-1}{2}}=-1$, and we must be in the second case since $a$ has order $p-1$.

Now $-1\in\mathbb{Z}_p^*$ is a square if and only if it is an even power of $a$, so substituting $4n+1$ and $4n+3$ for $p$ in the above tells you that this only happens if $p=4n+1$.

share|improve this answer
1  
This too works without change in any finite field. –  Marc van Leeuwen Mar 19 '12 at 13:38

$-1 \equiv x^2\ mod\ p$ implies that $(-1)^{\varphi(p)/2} = 1$. This result follows from Euler's criterion that for any $\alpha \in Z_p^*$, if $\alpha \in (Z_p^*)^2$, then $\alpha^{\varphi(p)/2} = 1$ and if $\alpha \notin (Z_p^*)^2$, then $\alpha^{\varphi(p)/2} = -1$.
So for $Z_p^*$, we have $\varphi(p) = p-1$. Hence $\varphi(p)/2 = (p-1)/2$.
If $p \equiv 1\ (mod\ 4)$, then $(p-1)/2$ is even and if $p \equiv 3\ (mod\ 4)$ then $(p-1)/2$ is odd.
So if $p \equiv 1\ (mod\ 4)$, then $(-1)^{(p-1)/2} = 1 \implies -1 \in (Z_p^*)^2$.

share|improve this answer

If we are allowed to use the theory of Frobenius of prime ideals, then we could also show as follows:
A prime ideal $(p)$ splits in $\mathbb Q(i)$ if and only if $x^2+1\pmod p$ has a solution in integers. Now this is equivalent with the triviality of the Frobenius of $(p)$ in $\mathbb Q(i)$. Namely, it is equivalent with the condition $\zeta^p=\zeta$ where $\zeta=i$. This tells us that, when $p\not=2$, $(\dfrac{-1}{p})=1$ if and only $p\equiv 1\pmod 4$.

P.S. The reason to require $p\not=2$ is to guarantee that $(p)$ does not ramify in $\mathbb Q(i)$, so that we can apply the theorem of Dedekind to conclude as above.

Any error is welcomed to be pointed out.
Thanks for the attention.

share|improve this answer

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.