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 (→‎See also)
(→‎Solution)
Line 5: Line 5:
 
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.
  
 
==See also==
 
==See also==

Revision as of 11:47, 6 May 2011

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 counterexample.

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.

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=38348"