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...) |
(Added footer) |
||
Line 10: | Line 10: | ||
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 2^7 \pmod{25}</math> and thus <math>2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}</math>. Since <math>2^7</math> is not a power of <math>4</math>, we are done. | 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 2^7 \pmod{25}</math> and thus <math>2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}</math>. Since <math>2^7</math> is not a power of <math>4</math>, we are done. | ||
+ | |||
+ | ==See also== | ||
+ | {{USAMO newbox|year=2011|num-b=3|num-a=5}} |
Revision as of 10:38, 29 April 2011
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 counterexample.
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 for some , and thus not a power of .
Let for some odd prime . Then . Since 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 , we are done.
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 |