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.

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.
