Difference between revisions of "2011 USAMO Problems/Problem 4"
(Since 2^n is 1 mod (2^n-1), reduce the exponent mod n, we can't win with n prime, but n=p^2 will do...) |
|||
(20 intermediate revisions by 9 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.'' | ||
==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== | ||
We will show that <math>n = 25</math> is a counter-example. | We will show that <math>n = 25</math> is a counter-example. | ||
− | Since <math>2^n \equiv 1 \pmod{2^n - 1}</math>, we see that for any integer <math>k</math>, <math>2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}</math>. Let <math>0 \le m < n</math> be the residue of <math>2^n \pmod n</math>. Note that since <math>m < n</math> and <math>n \ge 2</math>, necessarily <math>2^m < 2^n -1</math>, and thus the remainder in question is <math>2^m</math>. We want to show that <math>2^m \pmod {2^n-1}</math> is an odd power of | + | Since <math>\textstyle 2^n \equiv 1 \pmod{2^n - 1}</math>, we see that for any integer <math>k</math>, <math>\textstyle 2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}</math>. Let <math>0 \le m < n</math> be the residue of <math>2^n \pmod n</math>. Note that since <math>\textstyle m < n</math> and <math>\textstyle n \ge 2</math>, necessarily <math>\textstyle 2^m < 2^n -1</math>, and thus the remainder in question is <math>\textstyle 2^m</math>. We want to show that <math>\textstyle 2^m \pmod {2^n-1}</math> is an odd power of 2 for some <math>\textstyle n</math>, and thus not a power of 4. |
− | Let <math>n=p^2</math> for some odd prime <math>p</math>. Then <math>\varphi(p^2) = p^2 - p</math>. Since | + | Let <math>\textstyle n=p^2</math> for some odd prime <math>\textstyle p</math>. Then <math>\textstyle \varphi(p^2) = p^2 - p</math>. Since 2 is co-prime to <math>\textstyle p^2</math>, we have |
+ | <cmath>{2^{\varphi(p^2)} \equiv 1 \pmod{p^2}}</cmath> | ||
+ | and thus | ||
+ | <cmath>\textstyle 2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}.</cmath> | ||
− | Therefore, for a counter-example, it suffices that <math>2^p \pmod{p^2}</math> be odd. Choosing <math>p=5</math>, we have <math>2^5 = 32 \equiv 7 \pmod{25}</math>. Therefore, <math>2^{25} \equiv | + | Therefore, for a counter-example, it suffices that <math>\textstyle 2^p \pmod{p^2}</math> be odd. Choosing <math>\textstyle p=5</math>, we have <math>\textstyle 2^5 = 32 \equiv 7 \pmod{25}</math>. Therefore, <math>\textstyle 2^{25} \equiv 7 \pmod{25}</math> and thus |
+ | <cmath>\textstyle 2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}.</cmath> | ||
+ | Since <math>\textstyle 2^7</math> is not a power of 4, we are done. | ||
+ | |||
+ | ==Solution 2== | ||
+ | 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 <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 <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 <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}} | ||
+ | |||
+ | ==See also== | ||
+ | |||
+ | {{USAMO newbox|year=2011|num-b=3|num-a=5}} | ||
+ | |||
+ | [[Category: Olympiad Number Theory Problems]] |
Latest revision as of 14: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
[hide]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 |