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