Elementary proof that $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$ I am trying to proof that  $-1$ is a square in $\mathbb{F}_p$ for $p = 1 \mod{4}$. Of course, this is really easy if one uses the Legendre Symbol and Euler's criterion. However, I do not want to use those. In fact, I want to prove this using as little assumption as possible.
What I tried so far is not really helpful:
We can easily show that $\mathbb{F}_p^*/(\mathbb{F}_p^*)^2 = \{ 1\cdot (\mathbb{F}_p^*)^2, a\cdot (\mathbb{F}_p^*)^2 \}$ where $a$ is not a square (this $a$ exists because the map $x \mapsto x^2$ is not surjective). Now $-1 = 4\cdot k = 2^2 \cdot k$ for some $k\in \mathbb{F}_p$.
From here I am trying to find some relation between $p =1 \mod{4}$ and $-1$ not being a multiple of a square and a non-square.
 A: You can use Wilson's theorem: $(p-1)!\equiv-1\pmod p$ and then show that $$(p-1)!\equiv 1\cdot 2\cdots \frac{p-1}{2} \left(-\frac{p-1}{2}\right)\cdots(-2)(-1) = \left(\left(\frac{p-1}{2}\right)!\right)^2(-1)^{\frac{p-1}{2}}\pmod p$$
This gives an exactly formula for a solution of $a^2=-1$, although not an efficient one: $a=\left(\frac{p-1}{2}\right)!$.
Wilson's theorem can be shown pretty directly by comparing $x^{p-1}-1$ and $(x-1)(x-2)\cdots(x-(p-1))$.
More generally, if $\mathbb F_q$ is a field with $q$ elements, $q$ odd, then the product of all the elements of $\mathbb F_q^\times$ is $-1$, because we can pair $a$ with $a^{-1}$ except for $a=-1$ and $a=1$. So you can show that $-1$ is a square in $\mathbb F_q$ if $q\equiv 1\pmod 4$ using the same argument.
Or you can factor $$x^{p-1}-1 = \left(x^{\frac{p-1}{2}}-1\right)\left(x^{\frac{p-1}{2}}+1\right)$$
The left side has $p-1$ roots, and thus $x^{\frac{p-1}{2}}+1$ must have a root, let's call it $a$. Then $(a^{\frac{p-1}{4}})^2=-1$ if $a$ is such a root.
A: On $\mathbb{F}_p^\ast$, define the equivalence relation
$$x\sim y :\!\!\iff (x = y) \lor (x = -y) \lor (xy = 1) \lor (xy = -1).$$
Generally, the equivalence class of $x$ has four elements, $\{ x, -x, x^{-1}, -x^{-1}\}$. Since we always have $x \neq -x$, every class has at least two elements, and if $x = x^{-1}$ or $x = -x^{-1}$, then the equivalence class of $x$ has precisely two elements. The case $x = x^{-1}$ (or $x^2 = 1$) yields the class $\{1,-1\}$, so there is always at least one class with two elements.
If $p \equiv 1 \pmod{4}$, the number of elements of $\mathbb{F}_p^\ast$ is divisible by $4$, therefore the number of two-element classes must be even, hence $2$, and that means there must be an $x$ with $x = -x^{-1}$, or $x^2 = -1$.
A: For $p\ge 3$, $\mathbb F_p^*$ is a cyclic group of order $p-1$. If $g$ is a generator, then $g^\frac{p-1}2= -1$. In particular $-1$ will be a square if and only if $\frac{p-1}{2}$ is even - i.e. if $p \equiv 1 \pmod 4$.
Note that this proof isn't fundamentally different from those using Fermat's little theorem. Indeed utilising the group theoretic structure of $\mathbb F_p^*$ gives one way of proving it.
