Difference between revisions of "2003 Polish Mathematical Olympiad Problems/Problem 3"
(problem and solutions) |
m (→Solution 2) |
||
(2 intermediate revisions by one other user not shown) | |||
Line 11: | Line 11: | ||
=== Solution 1 === | === Solution 1 === | ||
− | Suppose that for some <math>n</math>, <math>W(n) \neq \pm 1</math>. Then <math>W(n)</math> has a prime divisor <math>q</math> which divides <math>2^n-1</math>. (In particular, <math>q</math> is odd.) Evidently, <math>W(n+q) \equiv W(n) \equiv 0 \pmod{q}</math>, so <math>q</math> also divides <math>W(n+q)</math>, which divides <math>2^{n+q}-1</math>. Thus <math>2^{n+q} \equiv 1 \equiv 2^n \pmod{q}</math>. Since <math>q</math> is an odd prime, we may divide by <math>2^n</math> to obtain <math>2^q \equiv 1 pmod{q}</math>. But by [[Fermat's Little Theorem]], <math>2^q \equiv 2 \pmod{q}</math>, so <math>2 \equiv 1 \pmod{q}</math>, a contradiction. | + | Suppose that for some <math>n</math>, <math>W(n) \neq \pm 1</math>. Then <math>W(n)</math> has a prime divisor <math>q</math> which divides <math>2^n-1</math>. (In particular, <math>q</math> is odd.) Evidently, <math>W(n+q) \equiv W(n) \equiv 0 \pmod{q}</math>, so <math>q</math> also divides <math>W(n+q)</math>, which divides <math>2^{n+q}-1</math>. Thus <math>2^{n+q} \equiv 1 \equiv 2^n \pmod{q}</math>. Since <math>q</math> is an odd prime, we may divide by <math>2^n</math> to obtain <math>2^q \equiv 1 \pmod{q}</math>. But by [[Fermat's Little Theorem]], <math>2^q \equiv 2 \pmod{q}</math>, so <math>2 \equiv 1 \pmod{q}</math>, a contradiction. |
Thus <math>W(n) = \pm 1</math>, for all <math>n</math>. Since all polynomials bounded over the integers are constant, it follows that <math>W=1</math> and <math>W=-1</math> are the only solutions, as desired. <math>\blacksquare</math> | Thus <math>W(n) = \pm 1</math>, for all <math>n</math>. Since all polynomials bounded over the integers are constant, it follows that <math>W=1</math> and <math>W=-1</math> are the only solutions, as desired. <math>\blacksquare</math> | ||
Line 25: | Line 25: | ||
− | Let <math>a_0</math> be the | + | Let <math>a_0</math> be the constant term of <math>W</math>. Suppose that <math>p</math> is a [[prime]] such that <math>p \mid a_0</math>. Then <math>p \mid W(p) \mid 2^p -1</math>. But by [[Fermat's Little Theorem]], <math>2^p -1 \equiv 1 \pmod{p}</math>, so <math>p \nmid 2^p -1</math>, a contradiction. Therefore <math>a_0</math> is not divisible by any prime, so <math>a_0 = \pm 1</math>. Without loss of generality, let <math>a_0=1</math> (we note that if <math>W</math> satisfies the problem's conditions, then so does <math>-W</math>). |
We next note that <math>W(1) \mid 2^1-1 = 1</math>, so <math>W(1) = \pm 1</math>. We consider these two cases separately. | We next note that <math>W(1) \mid 2^1-1 = 1</math>, so <math>W(1) = \pm 1</math>. We consider these two cases separately. | ||
Line 43: | Line 43: | ||
Setting <math>x=n</math>, we have <math>(n) = n! Q(n) +1</math>. As noted in the lemma, this quantity exceeds <math>2^n-1</math> in absolute value if <math>Q(n) \neq 0</math>. Therefore <math>n</math> is not a counterexample, as before, so our claim holds. | Setting <math>x=n</math>, we have <math>(n) = n! Q(n) +1</math>. As noted in the lemma, this quantity exceeds <math>2^n-1</math> in absolute value if <math>Q(n) \neq 0</math>. Therefore <math>n</math> is not a counterexample, as before, so our claim holds. | ||
− | Since <math>W(x)-1</math> has infinitely many roots, it must be equal to zero. Therefore <math>W(x) =1</math> is the only possibility for a positive constant term; <math>W(x)=-1</math> is, of course, the only other possibility. <math>\ | + | Since <math>W(x)-1</math> has infinitely many roots, it must be equal to zero. Therefore <math>W(x) =1</math> is the only |
+ | possibility for a positive constant term; <math>W(x)=-1</math> is, of course, the only other possibility. <math>\blacksquare</math> | ||
Latest revision as of 22:29, 20 January 2016
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.