Problem 1405

1. Lemma Proof:
- Base Case: For $n = 1$, let $p(x)$ be a polynomial of degree 0 (a constant polynomial). If $p(x)$ is an integer for one integer value of $x$, it is trivially an integer for all $x \in \mathbb{Z}$.
- Inductive Step: Assume the lemma holds for some $n \geq 1$. Let $f(x)$ be a polynomial of degree $n$ such that $f(x)$ is an integer for $x = i, i+1, \ldots, i+n$. Consider the polynomial $q(x) = f(x+1) - f(x)$. The degree of $q(x)$ is $n-1$, and $q(x)$ is an integer for $x = i, i+1, \ldots, i+n-1$. By the induction hypothesis, $q(x)$ is an integer for every $x \in \mathbb{Z}$. Since $f(k+1) - f(k) = q(k)$, an induction on $k$ shows that $f(x)$ is an integer for every integer $x$.

2. Main Proof:
- Base Case: For $n = 0$, the polynomial $f(x)$ is a constant. The condition $\frac{f(x) - f(y)}{x - y}$ being an integer is trivially satisfied since $f(x) = f(y)$.
- Inductive Step: Assume the statement holds for $n-1$. Let $f(x)$ be a polynomial of degree $n$ that satisfies the given condition. Write $f(x) = x p(x) + f(0)$, where $p(x)$ is a polynomial of degree $n-1$. We have $p(x) = \frac{f(x) - f(0)}{x}$, which is an integer for $x = 1, 2, \ldots, n$. By the lemma, $p(x)$ is an integer for every $x \in \mathbb{Z}$. Thus, $\frac{f(x) - f(0)}{x}$ is an integer for every integer $x$.

3. **Consider the Polynomial $q(x) = f(x+1) - f(x)$:**
- The degree of $q(x)$ is $n-1$. We have $\frac{q(x) - q(y)}{x - y} = \frac{f(x+1) - f(y+1)}{(x+1) - (y+1)} - \frac{f(x) - f(y)}{x - y}$.
- By the given condition, $\frac{q(x) - q(y)}{x - y}$ is an integer for $0 \leq x < y \leq n-1$. By the induction hypothesis, $\frac{q(x) - q(y)}{x - y}$ is an integer for every distinct integers $x, y$.

4. Conclusion:
- Using the results from the lemma and the induction hypothesis, we conclude that $\frac{f(x) - f(y)}{x - y}$ is an integer for every distinct integers $x, y$.

Thus, $a - b \mid f(a) - f(b)$ for all distinct integers $a, b$.

$\blacksquare$