2011 USAMO Problems/Problem 4
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|