# 2003 Polish Mathematical Olympiad Problems/Problem 3

## Problem

Find all polynomials with integer coefficients satisfying the following condition: for every natural number , is divisible by .

*Note: The expression "natural number" is ambiguous, but this is irrelevant, as every integer is a divisor of .*

## Solutions

The only solutions are and .

### Solution 1

Suppose that for some , . Then has a prime divisor which divides . (In particular, is odd.) Evidently, , so also divides , which divides . Thus . Since is an odd prime, we may divide by to obtain . But by Fermat's Little Theorem, , so , a contradiction.

Thus , for all . Since all polynomials bounded over the integers are constant, it follows that and are the only solutions, as desired.

### Solution 2

**Lemma.** For all integers , , and for all integers , .

*Proof.* For the first statement, we induct on ; evidently, . Now, if and the lemma holds for , then , as desired.

For the second statement, we note that , , and . For the other integers less less than or equal to six, we have , from the lemma's first part.

Let be the constant term of . Suppose that is a prime such that . Then . But by Fermat's Little Theorem, , so , a contradiction. Therefore is not divisible by any prime, so . Without loss of generality, let (we note that if satisfies the problem's conditions, then so does ).

We next note that , so . We consider these two cases separately.

If , then 0 and 1 are roots of the polynomial ; hence there exists some polynomial such that . Setting , we have . But , and the only numbers equivalent to mod 30 which do not exceed 63 in absolute value are ; evidently, none of these divides 63. This is a contradiction. It follows that when .

If , then 0 and 1 are roots of the polynomial ; hence there exists some polynomial such that . Setting , we have . We note furthermore that , and that the only integers which do not exceed 63 in absolute value and which are congruent to 1 mod 30 are . Of these, only 1 is a divisor of 63; it follows that .

We now claim that every nonnegative integer is a root of the polynomial . Indeed, suppose that is the least counterexample. As we have already shown, .

If , then there exists some polynomial such that Setting , we have . But by the lemma, this quantity exceeds in absolute value if . Therefore , so , and is not a counterexample, a contradiction.

Similarly, if , then there exists a polynomial such that Setting , we have . As noted in the lemma, this quantity exceeds in absolute value if . Therefore is not a counterexample, as before, so our claim holds.

Since has infinitely many roots, it must be equal to zero. Therefore is the only possibility for a positive constant term; is, of course, the only other possibility.

*Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.*