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

Latest revision as of 14:41, 25 April 2021

The following problem is from both the 2011 USAJMO #6 and 2011 USAMO #4, so both problems redirect to this page.

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.

@@ Line 1: / Line 1: @@
+{{duplicate|[[2011 USAJMO Problems|2011 USAJMO #6]] and [[2011 USAMO Problems|2011 USAMO #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 <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==
 We will show that <math>n = 25</math> is a counter-example.
-Since <math>2^n \equiv 1 \pmod{2^n - 1}</math>, we see that for any integer <math>k</math>, <math>2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}</math>. Let <math>0 \le m < n</math> be the residue of <math>2^n \pmod n</math>. Note that since <math>m < n</math> and <math>n \ge 2</math>, necessarily <math>2^m < 2^n -1</math>, and thus the remainder in question is <math>2^m</math>. We want to show that <math>2^m \pmod {2^n-1}</math> is an odd power of <math>2</math> for some <math>n</math>, and thus not a power of <math>4</math>.
+Since <math>\textstyle 2^n \equiv 1 \pmod{2^n - 1}</math>, we see that for any integer <math>k</math>, <math>\textstyle 2^{2^n} \equiv 2^{(2^n - kn)} \pmod{2^n-1}</math>. Let <math>0 \le m < n</math> be the residue of <math>2^n \pmod n</math>. Note that since <math>\textstyle m < n</math> and <math>\textstyle n \ge 2</math>, necessarily <math>\textstyle 2^m < 2^n -1</math>, and thus the remainder in question is <math>\textstyle 2^m</math>. We want to show that <math>\textstyle 2^m \pmod {2^n-1}</math> is an odd power of 2 for some <math>\textstyle n</math>, and thus not a power of 4.
-Let <math>n=p^2</math> for some odd prime <math>p</math>. Then <math>\varphi(p^2) = p^2 - p</math>. Since <math>2</math> is co-prime to <math>p^2</math>, we have <math>2^{\varphi(p^2)} \equiv 1 \pmod{p^2}</math> and thus <math>2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}</math>.
+Let <math>\textstyle n=p^2</math> for some odd prime <math>\textstyle p</math>. Then <math>\textstyle \varphi(p^2) = p^2 - p</math>. Since 2 is co-prime to <math>\textstyle p^2</math>, we have
+<cmath>{2^{\varphi(p^2)} \equiv 1 \pmod{p^2}}</cmath>
+and thus
+<cmath>\textstyle 2^{p^2} \equiv 2^{(p^2 - p) + p} \equiv 2^p \pmod{p^2}.</cmath>
-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>\textstyle 2^p \pmod{p^2}</math> be odd. Choosing <math>\textstyle p=5</math>, we have <math>\textstyle 2^5 = 32 \equiv 7 \pmod{25}</math>. Therefore, <math>\textstyle 2^{25} \equiv 7 \pmod{25}</math> and thus
+<cmath>\textstyle 2^{2^{25}} \equiv 2^7 \pmod {2^{25} - 1}.</cmath>
+Since <math>\textstyle 2^7</math> is not a power of 4, we are done.
+==Solution 2==
+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 <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}}
+==See also==
+{{USAMO newbox|year=2011|num-b=3|num-a=5}}
+[[Category: Olympiad Number Theory Problems]]

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

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

Latest revision as of 14:41, 25 April 2021

Contents

Problem

Solution

Solution 2

See also