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

(12 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 
''This problem is from both the 2011 USAJMO and the 2011 USAMO, so both problems redirect here.''
 
''This problem is from both the 2011 USAJMO and the 2011 USAMO, so both problems redirect here.''
 
==Problem==
 
==Problem==
Consider the assertion that for each positive integer <math>n \ge 2</math>, the remainder upon dividing <math>2^{2^n}</math> by <math>2^n-1</math> is a power of 4. Either prove the assertion or find (with proof) a counterexample.
+
Consider the assertion that for each positive integer <math>n \ge 2</math>, the remainder upon dividing <math>2^{2^n}</math> by <math>2^n-1</math> is a power of 4. Either prove the assertion or find (with proof) a counter-example.
  
 
==Solution==
 
==Solution==
Line 18: Line 18:
  
 
==Solution 2==
 
==Solution 2==
Consider n = 25. We will prove that this case is a counterexample via contradiction.
+
Lemma (useful for all situations): If <math>x</math> and <math>y</math> are positive integers such that <math>2^x - 1</math> divides <math>2^y - 1</math>, then <math>x</math> divides <math>y</math>.
 +
Proof: <math>2^y \equiv 1 \pmod{2^x - 1}</math>. Replacing the <math>1</math> with a <math>2^x</math> and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise.
 +
 +
Consider <math>n = 25</math>. We will prove that this case is a counterexample via contradiction.
  
Because 4 = <math>2^2</math>, we will assume there exists a positive integer k such that <math>2^{2^n} - 2^{2k}</math> divides <math>2^n - 1</math> and <math>2^{2k} < 2^n - 1</math>. Dividing the powers of 2 from LHS gives <math>2^{2^n - 2k} - 1</math> divides <math>2^n - 1</math>. Hence, <math>2^n - 2k</math> divides n. Because n = 25 is odd, <math>2^24 - k</math> divides 25. Modular arithmetic gives <math>2^24 \equiv 2^4 \equiv 16 \pmod{25}</math> and so k = 16. However, <math>2^{2k} = 2^32 > 2^25 - 1</math>, a contradiction. Thus, n = 25 is a valid counterexample.
+
Because <math>4 = 2^2</math>, we will assume there exists a positive integer <math>k</math> such that <math>2^{2^n} - 2^{2k}</math> divides <math>2^n - 1</math> and <math>2^{2k} < 2^n - 1</math>. Dividing the powers of <math>2</math> from LHS gives <math>2^{2^n - 2k} - 1</math> divides <math>2^n - 1</math>. Hence, <math>2^n - 2k</math> divides <math>n</math>. Because <math>n = 25</math> is odd, <math>2^{24} - k</math> divides <math>25</math>. Euler's theorem gives <math>2^{24} \equiv 2^4 \equiv 16 \pmod{25}</math> and so <math>k \ge 16</math>. However, <math>2^{2k} \geq 2^{32} > 2^{25} - 1</math>, a contradiction. Thus, <math>n = 25</math> is a valid counterexample.
  
 
{{MAA Notice}}
 
{{MAA Notice}}
Line 27: Line 30:
  
 
{{USAMO newbox|year=2011|num-b=3|num-a=5}}
 
{{USAMO newbox|year=2011|num-b=3|num-a=5}}
 +
 +
[[Category: Olympiad Number Theory Problems]]

Revision as of 22:05, 3 May 2020

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 counter-example.

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.

Solution 2

Lemma (useful for all situations): If $x$ and $y$ are positive integers such that $2^x - 1$ divides $2^y - 1$, then $x$ divides $y$. Proof: $2^y \equiv 1 \pmod{2^x - 1}$. Replacing the $1$ with a $2^x$ and dividing out the powers of two should create an easy induction proof which will be left to the reader as an Exercise.

Consider $n = 25$. We will prove that this case is a counterexample via contradiction.

Because $4 = 2^2$, we will assume there exists a positive integer $k$ such that $2^{2^n} - 2^{2k}$ divides $2^n - 1$ and $2^{2k} < 2^n - 1$. Dividing the powers of $2$ from LHS gives $2^{2^n - 2k} - 1$ divides $2^n - 1$. Hence, $2^n - 2k$ divides $n$. Because $n = 25$ is odd, $2^{24} - k$ divides $25$. Euler's theorem gives $2^{24} \equiv 2^4 \equiv 16 \pmod{25}$ and so $k \ge 16$. However, $2^{2k} \geq 2^{32} > 2^{25} - 1$, a contradiction. Thus, $n = 25$ is a valid counterexample.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

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