## Number of congruence classes

How many classes of solutions are there to $x^2-1 \equiv 0 \pmod{168}$

So I did this:

1. Let a be the number of the classes of solutions to $x^2-1 \equiv 0 \pmod{2^3}$

2. Let b be the number of the classes of solutions to $x^2-1 \equiv 0 \pmod{3}$

3. Let c be the number of the classes of solutions to $x^2-1 \equiv 0 \pmod{7}$

So the classes of solutions to $x^2-1 \equiv 0 \pmod{168}$ is equal to $abc$

For case 1. We have $0, \pm 1, \pm 2, \pm 3, 4$ as congruence classes and only $\pm 1$ and $\pm 3$ works so that's 4 classes of solutions.

For case 2. We have $0, \pm 1$ as congruence classes and only $\pm 1$ works so that's 2 classes of solutions.

For case 3. We have $0, \pm 1, \pm 2, \pm 3$ as congruence classes and only $\pm 1$ works so that's 2 classes of solutions.

So all together we have $2^4 = 16$ classes of solutions.

However what I'm wondering is, isn't this way a bit primitive because if I worked out the PPF of some number other than 168 and ended up with say $2^{100}$ as one of the prime powers, then I would have to work out the number of classes of solutions to $x^2-1 \equiv 0 \pmod{2^{100}}$ Which means I have to list out $0, \pm 1, \pm 2 \cdots$ then test each of them to see if they work, wouldn't that take ages? Is there a faster way other than plugging a solution from each class of solutions into the equation and seeing if it works?

Thanks.