If $p(x)$ is a polynomial with integer coefficients and $p(100)=100$ what is the maximum number of integer solutions to the equation $p(k)=k^3$

Question

If $p(x)$ has integer coefficients and $p(100)$ equals $100$ what is the maximum number of integer solutions $k$ to the equation $p(k)=k^3$.

I have tried hard to solve this problem but I could not figure it out. I tried some particular cases but got nowhere, could someone please show me how to get the answer.

Answer 1

The maximum number is $10$.

The question at hand is equivalent to:

Among all $f(x) = (x+100)^3 - p(x+100) \in \mathbb{Z}[x]$, if $f(0) = 100^3 - 100 = 999900$, what is the maximum number of distinct integer roots of $f(x)$?

To solve this, we will use an elementary fact:

If $\alpha$ is an integer root for $\tilde{f}(x) \in \mathbb{Z}[x]$, then $\tilde{f}(x) = (x-\alpha) \tilde{g}(x)$ for some $\tilde{g}(x) \in \mathbb{Z}[x]$.

Apply this to our $f(x)$. If $\alpha_1, \alpha_2, \ldots, \alpha_n$ is the collection of distinct integer roots of $f(x)$, we can find a polynomial $g(x) \in \mathbb{Z}[x]$ such that $$f(x) = g(x) \prod_{k=1}^n(x-\alpha_k)$$

In particular, this implies $$f(0) = (-1)^n g(0) \prod_{k=1}^n \alpha_k \implies \prod_{k=1}^n \alpha_k {\huge |} f(0)$$

To maximize $n$, the number of distinct roots for $f(x)$, we just need to split $f(0)$ into a product of as many divisors as possible.

Notice $f(0) = 999900 = 2^2 \cdot 3^2 \cdot 5^2 \cdot 11 \cdot 101$ is a product of $8$ divisors. Together with the two divisors $\pm 1$ we can throw in for free, the number of distinct integer roots is at most $8 + 2 = 10$. It is indeed possible to construct a $f(x)$ with $10$ distinct integer roots. Consider

$$\alpha_1, \alpha_2, \ldots, \alpha_{10} = \pm 1, \pm 2, \pm 3, \pm 5, 11, 101$$

We get one possible solution for $f(x)$ where $n$ is maximized to $10$. $$\begin{align} f(x) &= (x^2 - 1)(x^2 - 4)(x^2 - 9)(x^2 - 25)(x-11)(x-101)\\ &= x^{10}-112 x^9+1072 x^8+4368 x^7-42930 x^6-44688 x^5+442028 x^4\\ &\quad+ 141232 x^3-1400071 x^2-100800 x+ 999900 \end{align}$$ The corresponding $p(x)$ that have $10$ distinct integer roots is given by: $$\begin{align} p(x) &= x^3-g(x-100)\\ &= -x^{10} + 1112 x^9 - 551872 x^8 + 161173232 x^7 - 30705059470 x^6\\ &\quad+ 3990289006688 x^5 - 358464703286028 x^4 + 21992178045469969 x^3\\ &\quad- 882234798357910329 x^2 + 20904472307595126600 x\\ &\quad- 222240760927578369900 \end{align} $$

Answer 2

If $p(100)=100$ then $p(x)$ is of the form $$ p(x)=(x-100)q(x)+100 $$ with $q(x)$ being a polynomial with integer coefficients. Now $p(x)=x^3$ implies that $$(x-100)\mid(x^3-100),\tag{1}$$ hence: $$(x-100)\mid 999900=2^2\cdot 3^2\cdot 5^2\cdot 11\cdot 101. \tag{2}$$ This can happen only if $(x-100)$ is an integer divisor of $999900$, hence for no more than $$3\cdot 3\cdot 3\cdot 2\cdot 2\cdot 2 = 216$$ possible integer values of $x$. Now it is up to you to prove that we may have $216$ solutions (just use polynomial interpolation to find a good $q(x)$), or not. Consider that for any polynomial with integer coefficients, $(a-b)$ is always a divisor of $p(a)-p(b)$.