Putnam 2007, Problem B-1

Let $f$ be a polynomial with positive integer coefficients. Prove that if $n$ is a positive integer, then $f(n)$ divides $f(f(n)+1)$ if and only if $n = 1$. [Editor's note: one must assume $f$ is nonconstant.]

Solution:
The problem fails if $f$ is allowed to be constant, e.g., take $f(n) = 1$. We thus assume that $f$ is nonconstant. Write $f(n) = \sum_{i=0}^d a_i n^i$ with $a_i > 0$. Then
$$f(f(n) + 1) = \sum_{i=0}^d a_i (f(n) + 1)^i \equiv f(1) \pmod{f(n)}.$$
If $n = 1$, then this implies that $f(f(n) + 1)$ is divisible by $f(n)$. Otherwise, $0 < f(1) < f(n)$ since $f$ is nonconstant and has positive coefficients, so $f(f(n) + 1)$ cannot be divisible by $f(n)$.