2003 Polish Mathematical Olympiad Problems/Problem 3
Contents
[hide]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.