Difference between revisions of "2011 USAMO Problems/Problem 4"
(→Solution 2) |
|||
(9 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
+ | {{duplicate|[[2011 USAJMO Problems|2011 USAJMO #6]] and [[2011 USAMO Problems|2011 USAMO #4]]}} | ||
''This problem is from both the 2011 USAJMO and the 2011 USAMO, so both problems redirect here.'' | ''This problem is from both the 2011 USAJMO and the 2011 USAMO, so both problems redirect here.'' | ||
==Problem== | ==Problem== | ||
− | Consider the assertion that for each positive integer <math>n \ge 2</math>, the remainder upon dividing <math>2^{2^n}</math> by <math>2^n-1</math> is a power of 4. Either prove the assertion or find (with proof) a | + | Consider the assertion that for each positive integer <math>n \ge 2</math>, the remainder upon dividing <math>2^{2^n}</math> by <math>2^n-1</math> is a power of 4. Either prove the assertion or find (with proof) a counter-example. |
==Solution== | ==Solution== | ||
Line 18: | Line 19: | ||
==Solution 2== | ==Solution 2== | ||
− | Lemma (useful for all situations): If x and y are positive integers such that <math>2^x - 1</math> divides <math>2^y - 1</math>, then x divides y. | + | Lemma (useful for all situations): If <math>x</math> and <math>y</math> are positive integers such that <math>2^x - 1</math> divides <math>2^y - 1</math>, then <math>x</math> divides <math>y</math>. |
− | Proof: <math>2^y \equiv 1 \pmod{2^x - 1}</math>. Replacing the 1 with a <math>2^x</math> and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise. | + | Proof: <math>2^y \equiv 1 \pmod{2^x - 1}</math>. Replacing the <math>1</math> with a <math>2^x</math> and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise. |
− | Consider n = 25. We will prove that this case is a counterexample via contradiction. | + | Consider <math>n = 25</math>. We will prove that this case is a counterexample via contradiction. |
− | Because | + | Because <math>4 = 2^2</math>, we will assume there exists a positive integer <math>k</math> such that <math>2^{2^n} - 2^{2k}</math> divides <math>2^n - 1</math> and <math>2^{2k} < 2^n - 1</math>. Dividing the powers of <math>2</math> from LHS gives <math>2^{2^n - 2k} - 1</math> divides <math>2^n - 1</math>. Hence, <math>2^n - 2k</math> divides <math>n</math>. Because <math>n = 25</math> is odd, <math>2^{24} - k</math> divides <math>25</math>. Euler's theorem gives <math>2^{24} \equiv 2^4 \equiv 16 \pmod{25}</math> and so <math>k \ge 16</math>. However, <math>2^{2k} \geq 2^{32} > 2^{25} - 1</math>, a contradiction. Thus, <math>n = 25</math> is a valid counterexample. |
{{MAA Notice}} | {{MAA Notice}} | ||
Line 30: | Line 31: | ||
{{USAMO newbox|year=2011|num-b=3|num-a=5}} | {{USAMO newbox|year=2011|num-b=3|num-a=5}} | ||
+ | |||
+ | [[Category: Olympiad Number Theory Problems]] |
Latest revision as of 15:41, 25 April 2021
- The following problem is from both the 2011 USAJMO #6 and 2011 USAMO #4, so both problems redirect to this page.
This problem is from both the 2011 USAJMO and the 2011 USAMO, so both problems redirect here.
Contents
Problem
Consider the assertion that for each positive integer , the remainder upon dividing
by
is a power of 4. Either prove the assertion or find (with proof) a counter-example.
Solution
We will show that is a counter-example.
Since , we see that for any integer
,
. Let
be the residue of
. Note that since
and
, necessarily
, and thus the remainder in question is
. We want to show that
is an odd power of 2 for some
, and thus not a power of 4.
Let for some odd prime
. Then
. Since 2 is co-prime to
, we have
and thus
Therefore, for a counter-example, it suffices that be odd. Choosing
, we have
. Therefore,
and thus
Since
is not a power of 4, we are done.
Solution 2
Lemma (useful for all situations): If and
are positive integers such that
divides
, then
divides
.
Proof:
. Replacing the
with a
and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise.
Consider . We will prove that this case is a counterexample via contradiction.
Because , we will assume there exists a positive integer
such that
divides
and
. Dividing the powers of
from LHS gives
divides
. Hence,
divides
. Because
is odd,
divides
. Euler's theorem gives
and so
. However,
, a contradiction. Thus,
is a valid counterexample.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2011 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |