2
$\begingroup$

I've tried to solve it in the following way:

First let's solve $x^2+x\equiv 0\ (\mod10)$. Solutions are $-1, 0, 4, 5$.

So $-1$ and $0$ are obviously solutions of $x^2 + x \equiv 0\ (\mod 10^5)$. Now let's solve this for $4$ and $5$:

Let $x = 10k + 4$, then put this $x$ into $x^2 + x \equiv 0\ (\mod 100)$. So after a few operation we get $k=-2\ (\mod 10)$. Now let $l = 10k + 2$ and $x = 10\cdot (10k + 2) + 4$. Now we can solve our equation by modulo $1000$. Then we keep doing similar steps until modulo $10^5$ solution is found.

The problem is we need to operate really big numbers. And we need to do it twice (for both roots $4$ and $5$). Is there any less complicated solution?

$\endgroup$
  • 1
    $\begingroup$ $10^5$ is not that big. The less complicated solution would be to use the chinese remainder theorem (which you mention, but never use) to find a number that gives remainder 0 modulo $2^5$ and -1 modulo $5^5$, or vice versa. Come to think of it, this is actually more complicated. $\endgroup$ – Ivan Neretin Oct 12 '15 at 18:50
4
$\begingroup$

$10 = 2 \times 5$, so you should really do this mod $2^5$ and mod $5^5$ and use CRT. Since $x^2 + x = x (x + 1)$ and $\gcd(x,x+1) = 1$, $x^2+x \equiv 0 \mod p^n$ (where $p$ is prime) iff either $x \equiv 0 \mod p^n$ or $x \equiv -1 \mod p^n$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

To expand just a bit on Robert’s answer, in addition to $0$ and $99999$, which are already congruent to $0$ and $-1$ modulo $10^5$, you should be able to find $n$ that’s $\equiv0\pmod{32}$ and $\equiv-1\pmod{3125}$ and $m$ that’s $\equiv-1\pmod{32}$ and $\equiv0\pmod{3125}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

$x^2 + x = x (x+1)$ At most one of $x$ or $x+1$ is divisible by 2, and likewise by 5. So either one of them is divisible by $10^5$ or one is divisible by $5^5$ and the other by $2^5$.

To find solutions, consider odd multiples of $5^5 = 3125$, add or subtract 1, and see how what the largest power of 2 is that divides the result.

A bit of checking shows that $3\times 5^5 = 9375$, and $9376 = 32\times293$, so $x = 9375$ is a third solution.

| cite | improve this answer | |
$\endgroup$

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.