<s>[INST] What is the number of solution to $x^2\equiv 1\pmod{p^k}$? We learned about quadratic reciprocity and how it relates to the number of solution to $x^2 \equiv 1 \pmod{p}$. 
I was wondering, is there a general formula for the 
number of solutions modulo $p^k$ to $x^2 \equiv 1 \pmod{p^k}$?
Thank you very much!
 [/INST] If $p$ is odd, then $x^2\equiv 1\pmod{p}$ has exactly two solutions, because if $p\mid x^2-1=(x+1)(x-1)$, then either $p\mid x+1$ or $p\mid x-1$ (by Euclid's Lemma). The solutions are $x\equiv \pm 1\pmod{p}$.
$x^2\equiv 1\pmod{p^k},\, k\ge 2$ for an odd prime $p$ too has exactly two solutions $x\equiv \pm 1\pmod{p^k}$. This is because if $p^k\mid x^2-1=(x+1)(x-1)$, then assume for contradiction $p\mid x+1$ and $p\mid x-1$. But then $p\mid (x+1)-(x-1)=2$, so $p=2$; contradiction. We get either $p^k\mid x+1$ or $p^k\mid x-1$, i.e. $x\equiv \pm 1\pmod{p^k}$.
If $p=2$, then $x^2\equiv 1\pmod{2}$ has exactly one solution, namely $x\equiv 1\pmod{2}$. Also $x^2\equiv 1\pmod{2^k},\, k\ge 2$ has all the solutions given by $x\equiv \pm 1\pmod{2^{k-1}}$. This is because if $2^k\mid x^2-1=(x+1)(x-1)$, then $x+1,x-1$ are both even and $\gcd(x+1,x-1)=2$, so either $2^{k-1}\mid x+1$ or $2^{k-1}\mid x-1$.
$x\equiv \pm 1\pmod{2^{k-1}}$ gives $2$ solutions when $k=2$ (namely $x\equiv 1,3\pmod{4}$) and $4$ solutions given by $x\equiv 2^{k-1}l\pm 1\pmod{2^k},\, l\in\{0,1\}$ when $k\ge 3$.
</s>