2011 USAMO Problems/Problem 4
- 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.
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.
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.
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.
|2011 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|