# If $p$ is congruent to 1 mod 4 where $p$ is an odd prime, then $x^2$ congruent to -1 mod $p$ has 2 solutions.

If $$p = 5$$, then the values of $$x$$ that will satisfy the congruence $$x^2 \equiv -1 \bmod p$$ are $$2, 3$$

If $$p = 13$$, then the values of $$x$$ that will satisfy the above congruence are $$5, 8$$. And so on...

How can i prove that for all $$p$$ s.t. $$(p \equiv 1\bmod 4)$$, then $$x^2\equiv -1\bmod p$$ has only $$2$$ solutions? And by observation, I think it will also hold on $$p^k$$? How can I prove it though?

Thank you!

As mentioned, the case of prime $$p$$ is quadratic reciprocity. For $$p^k$$ you can use Hensel lifting. The point is this. Suppose $$x \in [1,2, \ldots, p^j-1]$$ is a solution of $$x^2 \equiv -1 \mod p^j$$, where $$p$$ is an odd prime and $$j \ge 1$$. Thus $$x^2 = -1 + z p^j$$ for some integer $$z$$. Consider $$x + p^j y$$ where $$y \in [0,1,\ldots, p-1]$$. We have $$(x + p^j y)^2 = x^2 + 2 p^j x y + p^{2j} y^2 \equiv -1 + (z + 2x y) p^j \bmod p^{j+1}$$ so $$x + p^j y$$ will be a solution mod $$p^{j+1}$$ iff $$y \equiv -z/(2 x) \bmod p$$. Thus every solution mod $$p^j$$ lifts to a unique solution mod $$p^{j+1}$$.
Induction on $$k$$ in $$p^k.$$ For $$k \geq 2,$$ we have two roots of $$-1 \pmod {p^{k-1}}.$$ Take one of them, call it $$r,$$ and pick a representative $$R$$ for $$r \pmod {p^k}.$$ We know that $$R^2 \equiv -1 + W p^{k-1} \pmod {p^k}$$ where $$W$$ is a value mod $$p,$$ if you wish, you may demand $$0 \leq W < p.$$
This $$R$$ then solve, for integer $$t,$$ $$\left( R + t p^{k-1} \right)^2 \equiv -1 \pmod {p^k} \; ?$$ $$R^2 + 2Rt p^{k-1} + t^2 p^{2k-2} \equiv -1 \pmod {p^k} \; ?$$ Since $$k \geq 2,$$ we have $$2k-2 \geq k.$$ $$R^2 + 2Rt p^{k-1} \equiv -1 \pmod {p^k} \; ?$$ $$-1 + W p^{k-1} + 2Rt p^{k-1} \equiv -1 \pmod {p^k} \; ?$$ $$W p^{k-1} + 2Rt p^{k-1} \equiv 0 \pmod {p^k} \; ?$$ $$W + 2Rt \equiv 0 \pmod p \; ?$$ Now, $$2R$$ is invertible $$\pmod p,$$ so there is one and only one solution $$\pmod p$$ to $$2Rt \equiv -W \pmod p \; ?$$
That's it, you get exactly one root on top of each root you have, in the process of going up one power of $$p$$