18
$\begingroup$

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.

  • 0
    If you mean [Lagrange's four-square theorem](http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem), then it is probably overkill if it works at all. See [Fermat's theorem on sums of two squares](http://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares). which points to several proofs.2012-03-19
  • 0
    Read up on the Legendre Symbol, which uses Euler's criterion, which can be proved with Lagrange's Theorem.2012-03-19
  • 0
    @ lhf I meant Lagrange's theorem in group theory. http://en.wikipedia.org/wiki/Lagrange's_theorem_(group_theory)2012-03-19
  • 0
    For the simpler theorem (which is equivalent to the sum of two squares theorem), you can use [Wilson's theorem](http://en.wikipedia.org/wiki/Wilson%27s_theorem#Applications).2012-03-19

7 Answers 7

24

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

  • 11
    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.2012-03-19
  • 0
    @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.2012-03-19
  • 0
    Sure, well done.2012-03-19
  • 0
    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.2012-03-19
  • 1
    @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$2012-03-19
  • 0
    Ok so I figured it out. Since the order of x is the smallest power of x that generates the identity, If x^2 generates -1 then (x^2)^2 generates 1. So therefore the order of x is 4. Then using fact given by Lagrange that the order of x must divide euler's totient function of p, we get 4 divides p-1. Therefore p is congruent to 1(mod4).2012-03-19
  • 0
    Oh I just saw your response, can you let me know if what I wrote makes some sense? Thank you.2012-03-19
  • 0
    @Mike: Yes it's correct, except that I find your use of the word "generate" a bit confusing :) I would rather say "x^2 equals -1 mod p".2012-03-19
20

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

  • 0
    [See also here](http://math.stackexchange.com/q/4872/242) for more on the group-theoretic viewpoint.2016-05-11
11

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

  • 1
    This too works without change in any finite field.2012-03-19
7

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$

4

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

3

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.

3

Assume $p>2$ prime.

$x^2=-1 \iff x^2+1=0 \iff \deg(x)=4$ (That means for is smaller for $n$ such that $x^n-1$). This means

$x^2+1 \mid x^{p-1}-1 \iff 4 \mid p-1$.

  • 0
    @NaN, why $\mid$ is important?2015-07-31