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"

m (→‎Problem)
m (→‎Solution 2)
Line 18: Line 18:
  
 
==Solution 2==
 
==Solution 2==
−
Lemma (useful for all situations): If x and y are positive integers such that <math>2^x - 1</math> divides <math>2^y - 1</math>, then x divides y.
+
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 1 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.
+
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 n = 25. We will prove that this case is a counterexample via contradiction.
+
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 (in particular, Euler's totient function for 25 equals 20) 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 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 (in particular, Euler's totient function for <math>25</math> equals <math>20</math>) gives <math>2^{24} \equiv 2^4 \equiv 16 \pmod{25}</math> and so <math>k \ge 16</math>. However, <math>2^{2k} >= 2^{32} > 2^{25} - 1</math>, a contradiction. Thus, <math>n = 25</math> is a valid counterexample.
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 15:22, 10 March 2017

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. Modular arithmetic (in particular, Euler's totient function for $25$ equals $20$) gives $2^{24} \equiv 2^4 \equiv 16 \pmod{25}$ and so $k \ge 16$. However, $2^{2k} >= 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=84613"