Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(Added footer)
 
(19 intermediate revisions by 9 users not shown)
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==
 
==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==
 
We will show that <math>n = 25</math> is a counter-example.
 
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==
 
==See also==
 +
 
{{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]]

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. AMC logo.png

See also

2011 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_USAMO_Problems/Problem_4&oldid=152654"