how to solve a quadratic congruence when the modulus is not square-free

Question

$ x^2\equiv1\pmod {12} $

This factors out to $ x^2\equiv1\pmod {3 \cdot 4} $

I've tried $ x^2\equiv1\pmod 3 $ and $x^2\equiv1\pmod 4 $

doesn't seem to work; how do I deal with prime squares?

Answer 1

How to solve $x^2\equiv1\pmod {4=2^2}$:

$x^2\equiv1\pmod4\iff x^2-1\equiv0\pmod4$

$\iff4|(x+1)(x-1) \iff 2|x-1 \iff x\equiv1\pmod2$

( $\iff x\equiv1$ or $3\pmod 4$).

Now you solve $x^2\equiv1\pmod{12} $ by solving $x\equiv1\pmod2$ and $x\equiv\pm1\pmod3$.

Answer 2

It's great idea to try to solve it because instead of 12 it can be much larger number. However for 12 I would use different approach:

1. Filter all even numbers because they cannot be solutions

2. Divide odd numbers into two groups: {1, 3, 5} and {-1, -3, -5}. Their solutions correspond.

3. Review cases 1, 3, 5, add the other group and get final answer.