Number of solutions $x \in \{1,2,\ldots, 1000 \}$ of $ x^2(x+1)^2 \equiv 0 \pmod{1000}$

Question

Since $1000 = 8\cdot 125$, I have calculated that $\lambda_f(8)=4$.Using the Hensel's Lemma, I found that $\lambda_f(125)=5$. However, it requires somewhat extensive calculations.

Is there a faster way to get around the problem?

Answer 1

Noting that $x$ and $x+1$ are relatively prime, one of $x^2$ and $(x+1)^2$ needs to be a multiple of $8$ and the other a multiple of $125$. This means that one of $x$ and $x+1$ must be a multiple of $4$ and the other must be a multiple of $25$.

Also note that if $k$ is a solution, so is $k+100$ and so is $k-100$, which means you only need to count the solutions in one interval of $100$.

These observations should make the problem quite reasonable to do quickly.

Edit: As noted by Aaron (thank you!), one could be a multiple of $100$ (i.e., one of $x$ and $x+1$ could be a multiple of $100$, and the other relatively prime to $100$).

Answer 2

Let $f(x)=x^2(x+1)^2$

$f(100+x)-f(x)\equiv 200x+600x^2+400x^3\equiv 200\,x\,(x+1)(2x+1)\pmod{1000}$

Yet we also have $f(x)\equiv 0\pmod 5\implies x\equiv 0\text{ or }4\pmod 5$ (by hand testing $0,1,2,3,4$).

We can verifies that $g(x)=x(x+1)(2x+1)\equiv 0\pmod 5$ also in this case.

Which means that $200g(x)\equiv 0\pmod{1000}$

so if $x$ is solution then $100+x$ is also solution

We can therefore limit ourselves in finding the solutions in the range $0\,..\,99$ (with unit digit $0,\ 4,\ 5$ or $9$) and multiply their number by $10$ to get all the solutions.

Let represent these numbers by $10k+r$ with $k=0\,..\,9$ and $r\in\{0,4,5,9\}$.

$f(10k)\equiv 100k^2\pmod{1000}\quad$ so we need $k=0$

$f(10k+4)\equiv 100(k^2+6k+4)\pmod{1000}\quad$ so we need $k=2$ (this one is less obvious than the others, I just tested all possibilities manually)

$f(10k+5)\equiv 100(k+3)^2\pmod{1000}\quad$ so we need $k=7$

$f(10k+9)\equiv 100(k+1)^2\pmod{1000}\quad$ so we need $k=9$

The possible solutions are then $\{0,24,75,99\}$

And we can conduct a verification to check they are effectively solutions of the original equation.

Overall there are $40$ solutions in $\mathbb Z/1000\mathbb Z$.

Answer 3

In order to determine the number of solutions, let's compute them for the prime powers that divide $1000$, namely $2^3$ and $5^3$. If $\#(f,n)$ denotes the number of solutions of $f(x)\equiv0$ modulo $n$, then due to the Chinese Remainder Theorem we have

$$\#(f, 1000) = \#(f, 8)\cdot \#(f, 125)\tag 1$$

The second thing to note is that, as we now are working mod prime-powers $p^k$, we have that at least one of $x$ or $x+1$ must be relative prime to $p$ and thus relative prime to $p^k$. This is because the numbers that are divisible by $p$ are $p$ places apart.

This means that if $x^2(x+1)^2\equiv 0$ then one of $x$ and $x+1$ must be a unit, and one of them is a non-unit, i.e. zero or a zero divisor. Same applies to $x^2$ and $(x+1)^2$. As we may divide by a unit without changing the number of solutions:

$$\#(x^2(x+1)^2, p^k) = \#(x^2, p^k) + \#((x+1)^2, p^k)\tag 2$$

Now $x\mapsto x+1$ is a bijection in $\Bbb Z/n\Bbb Z$, thus applying it won't change the number of solutions:

$$\#(x^2, n) = \#((x+1)^2, n) \tag 3$$

so that $(2)$ becomes

$$\#(x^2(x+1)^2, p^k) = 2\cdot \#(x^2, p^k) \tag 4$$

What's left is to determine the number of solutions of $x^2\equiv0 \mod p^3$ which are exactly the numbers that can be represented as $x=p^2y$. There are exactly $p=p^3/p^2$ such numbers in $\Bbb Z/p^3\Bbb Z$. Hence:

$$\#(x^2,p^3) = p\tag 5$$

Putting it all together:

$$\begin{align} \#(x^2(x+1)^2, 1000) &\stackrel{(1)}= \#(x^2(x+1)^2, 2^3) \cdot \#(x^2(x+1)^2, 5^3) \\ &\stackrel{(4)}= 2\#(x^2, 2^3) \cdot 2\#(x^2, 5^3) \\ &\stackrel{(5)}= 2\cdot2\cdot 2\cdot5 \\ &= 40 \\ \end{align}$$

As you exclude $x\equiv0\mod1000$ for some reason, there are 39 solutions to your equation.

---

It's not clear to me why numbers that satisfy $x^2≡0\pmod{p^3}$ can be represented as $x=p^2y$.

$x^2≡0\mod{p^3}$ means $x^2 = ap^3$ for some $a\in\Bbb Z$, i.e. $x^2$ is divisible by $p$ at least 3 times. Thus $x$ is divisible by $p$ at least 1.5 times. As exponents are integers, $p$ divides $x$ at least 2 times, i.e. $x=p^2y$ for some $y\in\Bbb Z$.