Problem 1294

In the solution to the preparatory task D of Series III, we proved that if polynomials $f$ and $g$ have integer coefficients, $\mathrm{st} f \leq \mathrm{st} g$, and for every natural number $n$, the number $f(n)$ is a divisor of the number $g(n)$, then there exists an integer $c$ such that $g(x) = c \cdot f(x)$. Therefore, either $\mathrm{st} f = \mathrm{st} g$ (when $c \ne 0$), or $g$ is the zero polynomial (when $c = 0$). It is sufficient to consider the case where $\mathrm{st} g > \mathrm{st} f$.

Let $h$ and $r$ be the quotient and remainder, respectively, of the division of the polynomial $g$ by $f$. Then

Polynomials $h$ and $r$ have rational coefficients. Let $a$ be the least common denominator of the coefficients of polynomials $h$ and $r$. Then the polynomials $H = ah$ and $R = ar$ have integer coefficients, and multiplying equation (1) by $a$ on both sides, we obtain

Therefore, the polynomial $ag$ also has integer coefficients.
For every natural number $n$, the number $f(n)$ is, of course, a divisor of the number $ag(n)$. Therefore, by (2), the number $f(n)$ is a divisor of the number $R(n) = ag(n) - H(n) \cdot f(n)$ for $n=1,2, \ldots$. Since $\mathrm{st} R = \mathrm{st} r < \mathrm{st} f$, it follows from the initial remark in this solution that $R = ar$ is the zero polynomial. Therefore, $r$ is also the zero polynomial, and from (1) we obtain $g = hf$.

We will show by example that the coefficients of the polynomial $h$ may not be integers. Let $f(x) = 2$, $g(x) = x^2 + x$. For every integer $n$, the number $g(n) = n(n + 1)$ is even, because one of the numbers $n$ and $n+1$ is even. Therefore, the number $f(n) = 2$ is a divisor of the number $g(n)$ for $n = 1, 2, \ldots$. The coefficients of the polynomial $\displaystyle h(x) = \frac{g(x)}{f(x)} = \frac{1}{2} x^2 + \frac{1}{2} x$ are, of course, not integers.