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"

(problem and solutions)
 
m (typo)
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>

Revision as of 22:36, 2 January 2008

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 leading coefficient 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. $\qed$ (Error compiling LaTeX. Unknown error_msg)


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=21774"