Difference between revisions of "2011 USAMO Problems/Problem 4"
(→Solution 2) |
(→Solution 2) |
||
Line 23: | Line 23: | ||
Consider <math>n = 25</math>. 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 <math>4 = 2^2</math>, we will assume there exists a positive integer k 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 2 from LHS gives <math>2^{2^n - 2k} - 1</math> divides <math>2^n - 1</math>. Hence, <math>2^n - 2k</math> divides n. Because n = 25 is odd, <math>2^{24} - k</math> divides 25. Modular arithmetic (in particular, Euler's totient function for <math>25</math> equals <math>20</math>) gives <math>2^{24} \equiv 2^4 \equiv 16 \pmod{25}</math> and so <math>k \ge 16</math>. However, <math>2^{2k} >= 2^{32} > 2^{25} - 1</math>, a contradiction. Thus, <math>n = 25</math> is a valid counterexample. | + | 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>. Modular arithmetic (in particular, Euler's totient function for <math>25</math> equals <math>20</math>) gives <math>2^{24} \equiv 2^4 \equiv 16 \pmod{25}</math> and so <math>k \ge 16</math>. However, <math>2^{2k} >= 2^{32} > 2^{25} - 1</math>, a contradiction. Thus, <math>n = 25</math> is a valid counterexample. |
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 16:23, 10 March 2017
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
. Modular arithmetic (in particular, Euler's totient function for
equals
) 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 |