What is the number of solution to $x^2\equiv 1\pmod{p^k}$?

Question

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!

Answer 1

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$.

Answer 2

For prime $p$ and positive integer $k$, multiplication $\pmod {p^k}$ on the integers not divisible by $p$ is a group $G(p,k)$.The number of members of $G(p,k)$ is $\phi (p^k)=(p-1)p^{k-1} . $ THEOREM :When $p$ is odd, $G(p,k)$ is a cyclic group.....COROLLARY: When $p$ is odd, there are exactly two solutions, $\pmod {p^k}$, to $x^2\equiv 1 \pmod {p^k}$. The theorem is proven by elementary means, but not so short.Perhaps someone can provide a reference to a textbook.