Difference between revisions of "2011 USAMO Problems/Problem 4"

(Since 2^n is 1 mod (2^n-1), reduce the exponent mod n, we can't win with n prime, but n=p^2 will do...)
 
(Added footer)
Line 10: Line 10:
  
 
Therefore, for a counter-example, it suffices that <math>2^p \pmod{p^2}</math> be odd. Choosing <math>p=5</math>, we have <math>2^5 = 32 \equiv 7 \pmod{25}</math>. Therefore, <math>2^{25} \equiv 2^7 \pmod{25}</math> and thus <math>2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}</math>. Since <math>2^7</math> is not a power of <math>4</math>, we are done.
 
Therefore, for a counter-example, it suffices that <math>2^p \pmod{p^2}</math> be odd. Choosing <math>p=5</math>, we have <math>2^5 = 32 \equiv 7 \pmod{25}</math>. Therefore, <math>2^{25} \equiv 2^7 \pmod{25}</math> and thus <math>2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}</math>. Since <math>2^7</math> is not a power of <math>4</math>, we are done.
 +
 +
==See also==
 +
{{USAMO newbox|year=2011|num-b=3|num-a=5}}

Revision as of 10:38, 29 April 2011

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 $2^n \equiv 1 \pmod{2^n - 1}$, we see that for any integer $k$, $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 $m < n$ and $n \ge 2$, necessarily $2^m < 2^n -1$, and thus the remainder in question is $2^m$. We want to show that $2^m \pmod {2^n-1}$ is an odd power of $2$ for some $n$, and thus not a power of $4$.

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

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

See also

2011 USAMO (ProblemsResources)
Preceded by
Problem 3
Followed by
Problem 5
1 2 3 4 5 6
All USAMO Problems and Solutions
Invalid username
Login to AoPS