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

  • $\begingroup$ 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]$. $\endgroup$ – Jack D'Aurizio Aug 11 '14 at 10:22
  • $\begingroup$ Sorry, but what do the vertical lines mean? $\endgroup$ – Maxwell Aug 11 '14 at 10:47
  • $\begingroup$ $a\mid b$ means that $a$ is a divisor of $b$. $\endgroup$ – Jack D'Aurizio Aug 11 '14 at 11:01
  • $\begingroup$ @JackD'Aurizio OK, I take it back. It's trivial, for some reason I was trying to prove something harder >< $\endgroup$ – user2345215 Aug 11 '14 at 11:26
  • 2
    $\begingroup$ 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! $\endgroup$ – achille hui Aug 11 '14 at 12:36

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.