Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

m (typo)
m (→‎Solution 2)
 
(One intermediate revision by one other user not shown)
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.
 
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>\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>
  
  

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_Polish_Mathematical_Olympiad_Problems/Problem_3&oldid=74736"