Simple Congruence Problem -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.
 A: 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_{+}}$
A: 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$.
