2011 USAMO Problems/Problem 4

This problem is from both the 2011 USAJMO and the 2011 USAMO, so both problems redirect here.

Problem

Consider the assertion that for each positive integer $n \ge 2$ , the remainder upon dividing $2^{2^n}$ by $2^n-1$ is a power of 4. Either prove the assertion or find (with proof) a counterexample.

Solution

We will show that $n = 25$ is a counter-example.

Since $\textstyle 2^n \equiv 1 \pmod{2^n - 1}$ , we see that for any integer $k$ , $\textstyle 2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}$ . Let $0 \le m < n$ be the residue of $2^n \pmod n$ . Note that since $\textstyle m < n$ and $\textstyle n \ge 2$ , necessarily $\textstyle 2^m < 2^n -1$ , and thus the remainder in question is $\textstyle 2^m$ . We want to show that $\textstyle 2^m \pmod {2^n-1}$ is an odd power of 2 for some $\textstyle n$ , and thus not a power of 4.

Let $\textstyle n=p^2$ for some odd prime $\textstyle p$ . Then $\textstyle \varphi(p^2) = p^2 - p$ . Since 2 is co-prime to $\textstyle p^2$ , we have ${2^{\varphi(p^2)} \equiv 1 \pmod{p^2}}$ and thus $\textstyle 2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}.$

Therefore, for a counter-example, it suffices that $\textstyle 2^p \pmod{p^2}$ be odd. Choosing $\textstyle p=5$ , we have $\textstyle 2^5 = 32 \equiv 7 \pmod{25}$ . Therefore, $\textstyle 2^{25} \equiv 7 \pmod{25}$ and thus $\textstyle 2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}.$ Since $\textstyle 2^7$ is not a power of 4, we are done.

2011 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2011 USAMO Problems/Problem 4

Problem

Solution

See also