LIV OM - III - Task 3

Determine all polynomials $ W $ with integer coefficients that satisfy the following condition: for every natural number $ n $, the number $ 2^n-1 $ is divisible by $ W(n) $.
Let $ W(x) = a_0 + a_1x +\ldots + a_rx^r $ be a polynomial with integer coefficients, satisfying the given condition. Suppose that for some natural number $ k $, the value $ W(k) $ is different from $ 1 $ and $ -1 $; it therefore has a prime divisor $ p $. Let $ m = k + p $. The difference $ W(m) - W(k) $ is the sum of differences of the form $ a_j(m^j - k^j) $, which are numbers divisible by $ m - k $, i.e., by $ p $. Therefore, $ W(m) $ is divisible by $ p $.
From the condition of the problem, it follows that $ p $ is a divisor of the numbers $ 2^k - 1 $ and $ 2^m - 1 $; it is therefore an odd prime divisor of the number $ 2^m - 2^k = 2^k (2^p - 1) $, i.e., it is a divisor of the number $ 2^p - 1 $. This, however, is not possible, because

the values of the binomial coefficient $ {p \choose i} $ are for $ i = 1,\ldots,p- 1 $ numbers divisible by $ p $.
The contradiction proves that $ W(n) = \pm 1 $ for every natural number $ n $. Hence, it follows that $ W $ is a polynomial identically equal to $ 1 $ or identically equal to $ -1 $. Of course, each of these two polynomials satisfies the postulated condition.