Chinese remainder theorem other way around

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)$.

• 8 and 125 have 1000 as a product, and don't have a common divisor. This is the only way to split $1000 = 2^3 5^3$ that way. Otherwise the Chinese remainder theorem does not apply. – Henno Brandsma Dec 21 '14 at 13:02
• $8$ and $125$ are coprime, whereas $10$ and $100$ are not. – Frank Vel Dec 21 '14 at 13:03
• So if you have a large number, lets say $a=p_1^{k_1}p_2^{k_2}....p_n^{k_n}$ you split it into $p_1^{k_1}$, ...., $p_n^{k_n}$? – DeanTheMachine Dec 21 '14 at 13:05
• For the CRT to work, the factors need to be pairwise prime. Hence we would normally split it into powers of distinct primes. – steven gregory Jul 20 '17 at 22:05

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$.

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.