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"

(→‎Solution 2)
m (→‎Problem)
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==

Revision as of 09:27, 27 November 2016

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 ≥ 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=81674"