<s>[INST] Suppose $p$ is an odd prime and there exists some integer $x$ such that $x^2 \equiv -1 \pmod{p}$. Prove that $p \equiv 1 \pmod{4}$. Suppose $p$ is an odd prime and there exists some integer $x$ such that $x^2 \equiv -1 \pmod{p}$. Prove that $p \equiv 1 \pmod{4}$. Use Fermat's Theorem. 
 [/INST] Let's call the order of $x$ to be the smallest positive integer power, $k$ so that $x^k \equiv 1 \mod p$.  We'll denote the order of $x$ as $|x|$.... (assuming some a power exists; which it won't if $x$ is not relatively prime to $p$.)
Clearly $x^{k|x| + j; 0 \le j < |x|} = (x^{|x|})^k*x^j \equiv 1^k*x^j\equiv x^j \mod p$ and furthermore $x^{m} \equiv 1 \mod p \iff m \equiv 0 \mod |x|$
.....
Okay we know 1) $x^2 \equiv -1\mod p$. 
And 2) Fermat's Theorem: $x^{p-1} \equiv 1 \mod p$.
For 1) It is easy to verify $|x| = 4$.  [$*$].
So 2) implies $p-1 \equiv 0 \mod 4$.
======
[$*$]If the order of $x$ were $1$ then $x\equiv 1\mod p \implies x^2 \equiv 1\not \equiv -1 \mod p$.
If the order of $x$ were $3$ then $1 \equiv x^3 = x*x^2 \equiv -x \mod p\implies x\equiv -1 \mod p \implies x^2 \equiv 1 \mod p$. 
And, of course $x^4 \equiv 1 \mod p$. 
[Note; this assumes $p > 2$ so $1 \not \equiv -1 \mod p$]
</s>