TITLE: Prove that if there exists an integer a such that $a^2 \equiv −1 \text{ (mod p) then } p ≡ 1 \text{ (mod 4)}$
QUESTION [0 upvotes]: Let p be a prime number which is not equal to 2. Prove that if there exists an integer a such that
$a^2 \equiv −1 \text{ (mod p) then }  p ≡ 1 \text{ (mod 4)}$
I am not sure how to solve this one. I know $p|a^2 + 1$, but I can't figure out how to relate this to p modulo 4.

REPLY [1 votes]: You know that $p \not\mid a$. Thus, by Fermat's little theorem, you have
$$a^{p-1} \equiv 1 \pmod p \tag{1}\label{eq1A}$$
Suppose that $p \equiv 3 \pmod 4$, so $p = 4k + 3$ for some integer $k \ge 0$. Since $a^2 \equiv -1 \pmod p$, then from \eqref{eq1A} you get
$$\begin{equation}\begin{aligned}
a^{4k + 2} & \equiv 1 \pmod p \\
(a^{2})^{2k + 1} & \equiv 1 \pmod p \\
(-1)^{2k + 1} & \equiv 1 \pmod p \\
-1 & \equiv 1 \pmod p \\
0 & \equiv 2 \pmod p
\end{aligned}\end{equation}\tag{2}\label{eq2A}$$
This is, of course, not possible for odd primes $p$. Thus, you must have that $p \equiv 1 \pmod 4$.
{"set_name": "stack_exchange", "score": 0, "question_id": 3573174}