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

  • $\begingroup$ 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. $\endgroup$ – Henno Brandsma Dec 21 '14 at 13:02
  • $\begingroup$ $8$ and $125$ are coprime, whereas $10$ and $100$ are not. $\endgroup$ – Frank Vel Dec 21 '14 at 13:03
  • $\begingroup$ 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}$? $\endgroup$ – DeanTheMachine Dec 21 '14 at 13:05
  • $\begingroup$ For the CRT to work, the factors need to be pairwise prime. Hence we would normally split it into powers of distinct primes. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.