Prove that $u^m \equiv -1\pmod p \iff p \equiv 1\pmod 4.$ 
Let $p$ be a prime number with $p \neq 2.$ Let $q = \frac {p-1} {2}$ and $u$ be an element of order $q$ modulo $p.$ Then show that there exists an integer $m$ such that $u^m \equiv -1 \pmod p$ if and only if $p \equiv 1\pmod 4.$

I tried it but failed to conclude. What I did is as follows. $$u^m \equiv -1\pmod p \implies u^{2m} \equiv 1\pmod p.$$ Hence $q\mid 2m.$ Which is same as saying $(p-1)\mid 4m.$ Now I got stuck. How do I proceed now? Any help will be warmly appreciated.
Thanks for your time.
 A: In one direction, if $p \equiv 1 \pmod 4$, then we may take $m = \frac q 2 = \frac {p - 1}4$. Since $u^{2m} = u^q \equiv 1\pmod p$, we see that $u^m \equiv \pm 1 \pmod p$. But $u^m \equiv 1 \pmod p$ would contradict the assumption that the order of $u$ is $q$, hence we have $u^m \equiv -1\pmod p$.
In the other direction, if there exists $m$ such that $u^m \equiv -1\pmod p$, then we have $(-1)^q \equiv u^{qm} \equiv 1 \pmod p$, which (as $p\neq 2$) implies that $q = \frac {p - 1}2$ is even, hence $p \equiv 1 \pmod 4$.
A: It is tagged group-theory, so let's sketch a simple conceptual proof using that
$\qquad -1 \in G\!=\!\langle u\rangle\!\iff\! G$ has elt of order $2$ $\!\iff\! 2\mid \#G =\frac{p-1}2\!$ $\iff\! 4\mid p\!-\!1$
Remark $ $ The only nontrivial part is the middle equivalence, i.e. that a cyclic group $G$ has a subgroup of order $k\!\iff\! k\mid \#G,\,$ provable very simply  using nothing deeper than the integer division algorithm. The proof in Whatsup's answer is just a special case of such when $\,k=2,\,$ and that method works more generally for $\,k = p\,$ any prime, i.e.
Theorem $ $ A cyclic group $\,G=\langle u\rangle$ has an elt of prime order $\,p\iff p\mid  q:=\#G $
Proof $\ \ (\Leftarrow)\ \ \ p\mid q \Rightarrow  (u^{q/p})^p\! = 1,\,$ and $\, u^{q/p}\!\neq 1\,$ by $\,o(u)=q,\,$ thus $\,o(u^{q/p}) = p$.
$(\Rightarrow)\ \ \ o(u^k)\!=\!p\Rightarrow u^{kp}\!=1\,$ thus $\, q\mid pk,\,$ but $\,p\nmid q\Rightarrow q\mid k \Rightarrow u^k\!=1,\,$ contra $\,o(u^k)\!=\!p$.
