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!
 A: 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}$.   
A: 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$
This is the finite calculation that leads to Hensel's Lemma. I see that Robert calls it Hensel Lifting, I was not sure about the name.
