$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. May 8, 2013 at 21:39
• Thanks, I'll remember that. May 8, 2013 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^3\cdot 5\cdot 7$. Four solutions mod 8, two mod 5, two mod 7, so there will be $4\cdot 2\cdot 2= 16$ solutions mod 280.