# $x^2 = 1$ in the ring $\mathbb{Z}/n \mathbb{Z}$

I need to solve this equation:

$x^2 = 1$ in the ring $\mathbb{Z}/n \mathbb{Z}$.

I know that $(n - 1)(n - 1) \equiv 1 \pmod n$, in general $(n-a)^2 \equiv a^2 \pmod n$.

I also know that for $p$ prime all elements of $\mathbb{Z}_p$ are invertible and here $1$ and $p-1$ are their own inverses.

Could you tell me what other solutions there are to this equation?

-
Notice my edit. It's standard TeX usage. –  Michael Hardy May 8 '13 at 21:39
Thanks, I'll remember that. –  Colby May 8 '13 at 22:21

You need to solve it for each prime power dividing $n$, then combine the results with the Chinese Remainder Theorem.
For odd prime $p$, $x^2-1\equiv 0\pmod{p}$ has at most 2 solutions, and in fact exactly two since $1, -1$ are solutions. By Hensel's lemma, this will remain true for any power of $p$, since the derivative of $x^2-1$ is $2x\not \equiv 0\pmod{p}$.
Example: $n=280=2^357$. Four solutions mod 8, two mod 5, two mod 7, so there will be $4\cdot 2\cdot 2= 16$ solutions mod 280.