Chinese remainder theorem other way around

Question

I need to solve the following equation:

$x^2\equiv 1 (\textrm{mod }1000)$

According to the chinese remainder theorem I can rewrite this as:

$x^2 \equiv 1 (\textrm{mod }8)$ and $x^2 \equiv 1 (\textrm{mod }125)$
But I don't understand how I should know to which system of equations I should change to. Why not choose $\textrm{mod } 10$ for example. Or why not split the $x^2 \equiv 1 (\textrm{mod }8)$ into $x^2 \equiv 1 (\textrm{mod }2)$.

Then my other question is how do you solve these equations for larger numbers? Because for $x^2 \equiv 1 (\textrm{mod }8)$ I can find the solutions by simple trying but this will take to long for $x^2 \equiv 1 (\textrm{mod }125)$.

Answer 1

Your second question was how to solve the equation $x^2-1\equiv0\pmod{125}$. Because $125=5^3$, and $5$ is prime, $(x-1)$ and $(x+1)$ should in total have at least three factors $5$. Because $\gcd(x-1,x+1)\leq2$, it cannot happen that both $x-1$ and $x+1$ are divisible by $5$, so it follows that either $125\vert x+1$ and $5\nmid x-1$ or $125\vert x-1$ and $5\nmid x+1$.

Answer 2

Here's a useful theorem:

Lagrange's Theorem: If $f$ is a polynomial of degree $n$ and $p$ is prime, then the equation $$f(x) \equiv 0 \pmod p$$has at most $n$ solutions.

Note that if $f(x) \equiv 0 \pmod {p^k}$, then certainly $f(x) \equiv 0 \pmod {p^j}$ for any $j \le k$. This allows us to significantly reduce what we have to check.

For example, by Lagrange's theorem, $x^2-1 \equiv 0 \pmod 5$ has at most two solutions, which by observation must be $\pm 1$.

To solve $x^2 - 1 \equiv 0\pmod {25}$, we only need to check values of $x$ which are equivalent to $\pm 1 \pmod 5$ - i.e. $1,4,6,\ldots 24$. We discover that the possible solutions modulo $25$ are $\pm 1\pmod{25}$.

Then to solve $x^2 - 1 \pmod {125}$, we only need to check values of $x$ which are equivalent to $\pm 1 \pmod {25}$.

We can reduce things further than this, but this should probably be sufficient for your problem.