Problem:
Consider the assertion that for each positive integer n≥2, the remainder upon dividing 22n by 2n−1 is a power of 4. Either prove the assertion or find (with proof) a counterexample.
Solution:
The assertion is false, and the smallest n for which it fails is n=25. Given n≥2, let r be the remainder when 2n is divided by n. Then 2n=kn+r where k is a positive integer and 0≤r<n. It follows that
22n=2kn+r≡2rmod2n−1
and 2r<2n−1 so 2r is the remainder when 22n is divided by 2n−1. If r is even then 2r is power of 4 . Hence to disprove the assertion, it is enough to find an n for which the corresponding r is odd.
If n is even then so is r=2n−kn.
If n is an odd prime then 2n≡2(modn) by Fermat's Little Theorem; hence r≡2n≡2 modn and r=2.
There remains the case in which n is odd and composite. In the first three instances n=9, 15,21 there is no contradiction to the assertion:
n=9:26≡1mod9⇒29≡26⋅23≡8mod9
n=15:24≡1mod15⇒215≡(24)3⋅23≡8mod15
n=21:26≡1mod21⇒221≡(26)3⋅23≡8mod21
However,
210=1024≡−1⇒220≡1⇒225≡25≡7mod25
so 7 is the remainder when 225 is divided by 25 and 27 is the remainder when 2225 is divided by 225−1.
The problems on this page are the property of the MAA's American Mathematics Competitions