Simple Congruence Problem

Question

-1 is a square modulo an odd prime if and only if that prime is congruent to 1 mod 4.

Why is this, I cant seem to figure it out.

Answer 1

So suppose -1 is square modulo of an odd prime p. i.e for some integer x we have that $$x^{2} \equiv -1 \mod p$$ Evidently $\gcd(x,p)=1$, so applying Fermats Little Theorem gives $$(-1)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1 \mod p $$ But this can only hold if $\frac{p-1}{2}$ is even, i.e $p=4k+1$ , some $k\in \mathbb{Z_{+}}$

Answer 2

This is a consequence of Little Fermat: any integer $x\not\equiv 0\mod p$ satisfies the equation: $$a^{p-1}-1=0$$ As, if $p$ is odd, $a^{p-1}-1=\bigl(a^\tfrac{p-1}{2}-1\bigr)\bigl(a^\tfrac{p-1}{2}+1\bigr)$, each integer satisfies either $a^\tfrac{p-1}{2}-1=0$ or $a^\tfrac{p-1}{2}+1=0$, and each equation has $\dfrac{p-1}2$ solutions modulo $p$.

Now we have two cases:

• if $a$ is a square: $a\equiv b^2$, then $a^\tfrac{p-1}{2}-1=b^{p-1}-1=0$,
• if $a$ is not a square, $a^\tfrac{p-1}{2}+1=0$.

Let's set $a=-1$. If $p\equiv 1\mod4$, $\dfrac{p-1}2$ is even, so that we're in the first situation, which proves $-1$ is a square modulo $p$.

If $p\equiv3\mod 4$, $\dfrac{p-1}2$ is odd and we're in the second situation, which proves $-1$ is not a square modulo $p$.