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

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.

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}

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

• It is a consequence of the Ruffini's rule (en.wikipedia.org/wiki/Ruffini%27s_rule): if $100$ is a root of the polynomial $f(x)$ with integer coefficients, the remainder between $f(x)$ and $(x-100)$ is zero, hence we can write $f(x)$ as $g(x)(x-100)$ with $g\in\mathbb{Z}[x]$. – Jack D'Aurizio Aug 11 '14 at 10:22
• Sorry, but what do the vertical lines mean? – Maxwell Aug 11 '14 at 10:47
• $a\mid b$ means that $a$ is a divisor of $b$. – Jack D'Aurizio Aug 11 '14 at 11:01
• @JackD'Aurizio OK, I take it back. It's trivial, for some reason I was trying to prove something harder >< – user2345215 Aug 11 '14 at 11:26
• It is true that there are $216$ integers who can be a root of $p(x)$. However, any single $p(x)$ cannot contains all these roots at once. e.g if both $98 = 100 - 2$ and $102 = 100 + 2$ are roots of $p(x) - x^3$, then $94 = 100 - 6$ nor $106 = 100 + 6$ can be a root! – achille hui Aug 11 '14 at 12:36