Difference between revisions of "2003 Polish Mathematical Olympiad Problems/Problem 3"

Latest revision as of 22:29, 20 January 2016

Problem

Find all polynomials $W$ with integer coefficients satisfying the following condition: for every natural number $n$ , $2^n-1$ is divisible by $W(n)$ .

Note: The expression "natural number" is ambiguous, but this is irrelevant, as every integer is a divisor of $2^0 -1 = 0$ .

Solutions

The only solutions are $W=1$ and $W=-1$ .

Solution 1

Suppose that for some $n$ , $W(n) \neq \pm 1$ . Then $W(n)$ has a prime divisor $q$ which divides $2^n-1$ . (In particular, $q$ is odd.) Evidently, $W(n+q) \equiv W(n) \equiv 0 \pmod{q}$ , so $q$ also divides $W(n+q)$ , which divides $2^{n+q}-1$ . Thus $2^{n+q} \equiv 1 \equiv 2^n \pmod{q}$ . Since $q$ is an odd prime, we may divide by $2^n$ to obtain $2^q \equiv 1 \pmod{q}$ . But by Fermat's Little Theorem, $2^q \equiv 2 \pmod{q}$ , so $2 \equiv 1 \pmod{q}$ , a contradiction.

Thus $W(n) = \pm 1$ , for all $n$ . Since all polynomials bounded over the integers are constant, it follows that $W=1$ and $W=-1$ are the only solutions, as desired. $\blacksquare$

Solution 2

Lemma. For all integers $n\ge 4$ , $n! > 2^n$ , and for all integers $1 \le n \le 5$ , $(6-n) \cdot n! > 2^n$ .

Proof. For the first statement, we induct on $n$ ; evidently, $4! = 24 > 16 = 2^n$ . Now, if $n \ge 4$ and the lemma holds for $n-1$ , then $(n+1)! = (n+1) n! > 2 \cdot 2^n = 2^{n+1}$ , as desired.

For the second statement, we note that $(6-1) \cdot 1! = 6 > 2 = 2^1$ , $(6-2)2! = 8 > 4 = 2^2$ , and $(6-3) \cdot 3! = 18 > 8 = 2^3$ . For the other integers less less than or equal to six, we have $(6-n)n! \ge n! > 2^n$ , from the lemma's first part. $\blacksquare$

Let $a_0$ be the constant term of $W$ . Suppose that $p$ is a prime such that $p \mid a_0$ . Then $p \mid W(p) \mid 2^p -1$ . But by Fermat's Little Theorem, $2^p -1 \equiv 1 \pmod{p}$ , so $p \nmid 2^p -1$ , a contradiction. Therefore $a_0$ is not divisible by any prime, so $a_0 = \pm 1$ . Without loss of generality, let $a_0=1$ (we note that if $W$ satisfies the problem's conditions, then so does $-W$ ).

We next note that $W(1) \mid 2^1-1 = 1$ , so $W(1) = \pm 1$ . We consider these two cases separately.

If $W(1)=-1$ , then 0 and 1 are roots of the polynomial $W(x) - (-2x+1)$ ; hence there exists some polynomial $Q$ such that $W(x) = x(x-1) Q(x) - 2x+1$ . Setting $x=6$ , we have $W(6)\equiv 30 Q(6) -11 \equiv -11 \pmod{30}$ . But $W(6) \mid 2^6=63$ , and the only numbers equivalent to $-11$ mod 30 which do not exceed 63 in absolute value are $-41, -11, 19, 49$ ; evidently, none of these divides 63. This is a contradiction. It follows that $W(1) \neq -1$ when $a_0=1$ .

If $W(1)=1$ , then 0 and 1 are roots of the polynomial $W(x) -1$ ; hence there exists some polynomial $Q$ such that $W(x) = x(x-1)Q(x) +1$ . Setting $x=6$ , we have $W(6) = 30 Q(x) +1 \equiv 1 \pmod{30}$ . We note furthermore that $W(6) \mid 2^6-1 = 63$ , and that the only integers which do not exceed 63 in absolute value and which are congruent to 1 mod 30 are $-59, -29, 1, 31, 61$ . Of these, only 1 is a divisor of 63; it follows that $W(6)=1$ .

We now claim that every nonnegative integer is a root of the polynomial $W(x)-1$ . Indeed, suppose that $n$ is the least counterexample. As we have already shown, $n \neq 0, 1, 6$ .

If $n < 6$ , then there exists some polynomial $Q$ such that $W(x)-1 = x(x-1) \dotsm (x-(n-1))(x-6) Q(x) .$ Setting $x=n$ , we have $W(n) = - (6-n) n! Q(n) + 1$ . But by the lemma, this quantity exceeds $2^n-1$ in absolute value if $Q(n) \neq 0$ . Therefore $Q(n) =0$ , so $W(n)=1$ , and $n$ is not a counterexample, a contradiction.

Similarly, if $n > 6$ , then there exists a polynomial $Q$ such that $W(x) -1 = x(x-1) \dotsm (x-(n-1)) Q(x) .$ Setting $x=n$ , we have $(n) = n! Q(n) +1$ . As noted in the lemma, this quantity exceeds $2^n-1$ in absolute value if $Q(n) \neq 0$ . Therefore $n$ is not a counterexample, as before, so our claim holds.

Since $W(x)-1$ has infinitely many roots, it must be equal to zero. Therefore $W(x) =1$ is the only possibility for a positive constant term; $W(x)=-1$ is, of course, the only other possibility. $\blacksquare$

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

Resources

@@ Line 11: / Line 11: @@
 === 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>
@@ Line 25: / Line 25: @@
-Let <math>a_0</math> be the leading coefficient 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>).
+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.
@@ 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.
-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>\qed</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>

Page

Toolbox

Search