Writeup: Putnam 2007 B1

20 Jul, 2025

Problem Statement

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

My Solution

Let

f (n) = c_{0} x^{0} + c_{1} x^{1} + \dots c_{d} x^{d} .

Then we know that

f (f (n) + 1) = c_{0} + c_{1} (f (n) + 1) + c_{2} (f (n) + 1)^{2} + \dots c_{d} (f (n) + 1)^{d} .

Note that $(f (n) + 1)^{p} \equiv 1 mod f (n)$ always.

Then

f (f (n) + 1) \equiv c_{0} + c_{1} + c_{2} + \dots + c_{d} \equiv f (1) \equiv 0 mod f (n) .

But since we know that $f$ is monotonically increasing (it has positive integer coefficients), the only way that $f (n) | f (1)$ is if $f (n) = f (1)$ and therefore $n = 1$ .