Count the solutions of $x^2\equiv 1\pmod m$ I need to find how many incongruent solutions exist to the equation:
$x^2 \equiv 1(mod\space m)$.
I'm thinking I need to take a case by case approach, for example when $a = 0$, but these number theory problems are hard!
Thanks for the hints!
EDIT:
I suppose I should state what I've done.
If $x^2 \equiv 1 (mod \space m)$ has a solution, then necessarily, $x^2 \equiv 1(mod \space p_i^{b_i})$ has a solution too.  Then that means $x^2 \equiv 1(mod \space p_i)$ also has a solution, lastly taking me to this step:
$(x-1)(x+1) \equiv 0(mod \space p_i)$.
At this point, I'm not too sure where to go.
 A: Outline: We need to establish the following two basic facts.
(i) If $x^2\equiv 1\pmod{m}$ then $x^2\equiv 1\pmod{p_i^{b_i}}$ and $\pmod{2^a}$.
(ii) Suppose that $x_0^2\equiv 1\pmod{2^a}$ and $x_i^2\equiv 1\pmod{p_i^{b_i}}$. Let $x$ be the unique solution (modulo $m$) of the system of congruences $x\equiv x_0\pmod{2^a}$, $x\equiv x_i\pmod{p_i^{b_i}}$ guaranteed to exist by the Chinese Remainder Theorem. Then $x^2\equiv 1\pmod{m}$.

By (i) and (ii), it is enough to find (or at least count) the solutions of $x^2\equiv 1\pmod{2^a}$ and $\pmod{p_i^{b_i}}$.  Then we will know the solutions of $x^2\equiv 1\pmod{m}$, and will be able to count them.
The powers of odd primes are easy.  Note that $p_i$ cannot simultaneously divide each  of $x-1$ and $x+1$. Thus  $(x-1)(x+1)\equiv 0\pmod{p_i^{b_i}}$ if and only if $x\equiv 1\pmod{p_i^{b_i}}$ or $x\equiv -1\pmod{p_i^{b_i}}$.
The powers of $2$ are a little more complicated. The congruence $x_0^2\equiv 1\pmod{2}$ has $1$ solution. The congruence $x_0^2\equiv 1\pmod{4}$ has two. We show that if $a\ge 3$, then the congruence $x_0^2\equiv 1\pmod{2^a}$ has $4$ solutions. 
Note that if $a\gt 1$ any solution $x_0$ of the congruence is odd, so the gcd of $x_0-1$ and $x_0+1$ is equal to $2$. Thus  $(x_0-1)(x_0+1)\equiv 0\pmod{2^a}$ precisely if one of $x_0-1$ or $x_0+1$ is divisible by $2^{a-1}$. If $a\ge 3$ we get therefore the solutions $\pm 1$ and $2^{a-1}\pm 1$, and that's all. (In the case $a=1$, the $4$ solutions coincide, and in the case $a=2$ they coincide in pairs. If $a\ge 3$ they are distinct.)

Finally, we can count. If $a=0$ or $a=1$, the number of solutions is $2^r$. If $a=2$, then the number of solutions is $2^{r+1}$. And finally if $a\ge 3$, then the number of solutions is $2^{r+2}$.
