Home » 国际竞赛 » 数学国际竞赛 » AMC美国数学竞赛 » Details

2011 USAJMO Problems真题及答案

Category: AMC美国数学竞赛, 国际竞赛 Date: 2019年8月13日下午12:16

2011 USAJMO Problems真题及答案

完整版真题免费下载

+答案解析请参考文末

Day 1

Problem 1

Find, with proof, all positive integers? $n$ ?for which? $2^n + 12^n + 2011^n$ ?is a perfect square.

Problem 2

Let? $a$ ,? $b$ ,? $c$ ?be positive real numbers such that? $a^2 + b^2 + c^2 + (a + b + c)^2 le 4$ . Prove that $[frac{ab + 1}{(a + b)^2} + frac{bc + 1}{(b + c)^2} + frac{ca + 1}{(c + a)^2} ge 3.]$

Problem 3

For a point? $P = (a,a^2)$ ?in the coordinate plane, let? $ell(P)$ ?denote the line passing through? $P$ ?with slope? $2a$ . Consider the set of triangles with vertices of the form? $P_1 = (a_1, a_1^2)$ ,? $P_2 = (a_2, a_2^2)$ ,? $P_3 = (a_3, a_3^2)$ , such that the intersections of the lines? $ell(P_1)$ ,? $ell(P_2)$ ,? $ell(P_3)$ ?form an equilateral triangle? $Delta$ . Find the locus of the center of? $Delta$ ?as? $P_1 P_2 P_3$ ?ranges over all such triangles.

Day 2

Problem 4

A?word?is defined as any finite string of letters. A word is a?palindrome?if it reads the same backwards as forwards. Let a sequence of words? $W_0$ ,? $W_1$ ,? $W_2$ ,? $dots$ ?be defined as follows:? $W_0 = a$ ,? $W_1 = b$ , and for? $n ge 2$ ,? $W_n$ ?is the word formed by writing? $W_{n - 2}$ ?followed by? $W_{n - 1}$ . Prove that for any? $n ge 1$ , the word formed by writing? $W_1$ ,? $W_2$ ,? $dots$ ,? $W_n$ ?in succession is a palindrome.

Problem 5

Points? $A$ ,? $B$ ,? $C$ ,? $D$ ,? $E$ ?lie on a circle? $omega$ ?and point? $P$ ?lies outside the circle. The given points are such that (i) lines? $PB$ ?and? $PD$ ?are tangent to? $omega$ , (ii)? $P$ ,? $A$ ,? $C$ ?are collinear, and (iii)? $overline{DE} parallel overline{AC}$ . Prove that? $overline{BE}$ ?bisects? $overline{AC}$ .

Problem 6

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.

2011 USAJMO真题参考答案及详解

Problem 1

Solution 1

Let? $2^n + 12^n + 2011^n = x^2$ . Then? $(-1)^n + 1 equiv x^2 pmod {3}$ . Since all perfect squares are congruent to 0 or 1 modulo 3, this means that n must be odd. Proof by Contradiction: We wish to show that the only value of? $n$ ?that satisfies is? $n = 1$ . Assume that? $n ge 2$ . Then consider the equation? $2^n + 12^n = x^2 - 2011^n$ . From modulo 2, we easily know x is odd. Let? $x = 2a + 1$ , where a is an integer. $2^n + 12^n = 4a^2 + 4a + 1 - 2011^n$ . Dividing by 4,? $2^{n-2} + 3^n cdot 4^{n-1} = a^2 + a + dfrac {1}{4} (1 - 2011^n)$ . Since? $n ge 2$ ,? $n-2 ge 0$ , so? $2^{n-2}$ similarly, the entire LHS is an integer, and so are? $a^2$ ?and? $a$ . Thus,? $dfrac {1}{4} (1 - 2011^n)$ ?must be an integer. Let? $dfrac {1}{4} (1 - 2011^n) = k$ . Then we have? $1- 2011^n = 4k$ .? $1- 2011^n equiv 0 pmod {4}$ .? $(-1)^n equiv 1 pmod {4}$ . Thus, n is even. However, it has already been shown that? $n$ ?must be odd. This is a contradiction. Therefore,? $n$ ?is not greater than or equal to 2, and must hence be less than 2. The only positive integer less than 2 is 1.

Solution 2

If? $n = 1$ , then? $2^n + 12^n + 2011^n = 2025 = 45^2$ , a perfect square.

If? $n > 1$ ?is odd, then? $2^n + 12^n + 2011^n equiv 0 + 0 + (-1)^n equiv 3 pmod{4}$ .

Since all perfect squares are congruent to? $0,1 pmod{4}$ , we have that? $2^n+12^n+2011^n$ ?is not a perfect square for odd? $n > 1$ .

If? $n = 2k$ ?is even, then? $(2011^k)^2 < 2^{2k}+12^{2k}+2011^{2k}$ ? $= 4^k + 144^k + 2011^{2k} <$ ? $2011^k + 2011^k + 2011^{2k} < (2011^k+1)^2$ .

Since? $(2011^k)^2 < 2^n+12^n+2011^n < (2011^k+1)^2$ , we have that? $2^n+12^n+2011^n$ ?is not a perfect square for even? $n$ .

Thus,? $n = 1$ ?is the only positive integer for which? $2^n + 12^n + 2011^n$ ?is a perfect square.

Solution 3

Looking at residues mod 3, we see that? $n$ ?must be odd, since even values of? $n$ ?leads to? $2^n + 12^n + 2011^n = 2 pmod{3}$ . Also as shown in solution 2, for? $n>1$ ,? $n$ ?must be even. Hence, for? $n>1$ ,? $n$ ?can neither be odd nor even. The only possible solution is then? $n=1$ , which indeed works.

Solution 4

Take the whole expression mod 12. Note that the perfect squares can only be of the form 0, 1, 4 or 9 (mod 12). Note that since the problem is asking for positive integers,? $12^n$ ?is always divisible by 12, so this will be disregarded in this process. If? $n$ ?is even, then? $2^n equiv 4 pmod{12}$ ?and? $2011^n equiv 7^n equiv 1 pmod {12}$ . Therefore, the sum in the problem is congruent to? $5 pmod {12}$ , which cannot be a perfect square. Now we check the case for which? $n$ ?is an odd number greater than 1. Then? $2^n equiv 8 pmod{12}$ ?and? $2011^n equiv 7^n equiv 7 pmod {12}$ . Therefore, this sum would be congruent to? $3 pmod {12}$ , which cannot be a perfect square. The only case we have not checked is? $n=1$ . If? $n=1$ , then the sum in the problem is equal to? $2+12+2011=2025=45^2$ . Therefore the only possible value of? $n$ ?such that? $2^n+12^n+2011^n$ ?is a perfect square is? $n=1$ .

Problem 2

Solution 1

Since $begin{align*} (a+b)^2 + (b+c)^2 + (c+a)^2 &= 2(a^2 + b^2 + c^2 + ab + bc + ca) &= a^2 + b^2 + c^2 + (a + b + c)^2, end{align*}$ it is natural to consider a change of variables: $begin{align*} alpha &= b + c beta &= c + a gamma &= a + b end{align*}$ with the inverse mapping given by: $begin{align*} a &= frac{beta + gamma - alpha}2 b &= frac{alpha + gamma - beta}2 c &= frac{alpha + beta - gamma}2 end{align*}$ With this change of variables, the constraint becomes $[alpha^2 + beta^2 + gamma^2 le 4,]$ while the left side of the inequality we need to prove is now $begin{align*} & frac{gamma^2 - (alpha - beta)^2 + 4}{4gamma^2} + frac{alpha^2 - (beta - gamma)^2 + 4}{4alpha^2} + frac{beta^2 - (gamma - alpha)^2 + 4}{4beta^2} ge & frac{gamma^2 - (alpha - beta)^2 + alpha^2 + beta^2 + gamma^2}{4gamma^2} + frac{alpha^2 - (beta - gamma)^2 + alpha^2 + beta^2 + gamma^2}{4alpha^2} + frac{beta^2 - (gamma - alpha)^2 + alpha^2 + beta^2 + gamma^2}{4beta^2} = & frac{2gamma^2 + 2alphabeta}{4gamma^2} + frac{2alpha^2 + 2betagamma}{4alpha^2} + frac{2beta^2 + 2gammaalpha}{4beta^2} = & frac32 + frac{alphabeta}{2gamma^2} + frac{betagamma}{2alpha^2} + frac{gammaalpha}{2beta^2}. end{align*}$

Therefore it remains to prove that $[frac{alphabeta}{2gamma^2} + frac{betagamma}{2alpha^2} + frac{gammaalpha}{2beta^2} ge frac32.]$

We note that the product of the three (positive) terms is 1/8, therefore by AM-GM their mean is at least 1/2, and thus their sum is at least 3/2 and we are done.

Solution 2

Rearranging the condition yields that $[a^2 + b^2 + c^2 +ab+bc+ac le 2]$

Now note that $[frac{2ab+2}{(a+b)^2} ge frac{2ab+a^2 + b^2 + c^2 +ab+bc+ac}{(a+b)^2}=frac{(a+b)^2 + (c+a)(c+b)}{(a+b)^2}]$

Summing this for all pairs of? ${ a,b,c }$ ?gives that $[sum_{cyc} frac{2ab+2}{(a+b)^2} ge 3+ sum_{cyc}frac{(c+a)(c+b)}{(a+b)^2} ge 6]$

Problem 3

Solution 1

Note that all the points? $P=(a,a^2)$ ?belong to the parabola? $y=x^2$ ?which we will denote? $p$ . This parabola has a focus? $F=left(0,frac{1}{4}right)$ ?and directrix? $y=-frac{1}{4}$ ?which we will denote? $d$ . We will prove that the desired locus is? $d$ .

First note that for any point? $P$ ?on? $p$ , the line? $ell(P)$ ?is the tangent line to? $p$ ?at? $P$ . This is because? $ell(P)$ ?contains? $P$ ?and because? $[fracogiayisu0ku2{dx}] x^2=2x$ . If you don't like calculus, you can also verify that? $ell(P)$ ?has equation? $y=2a(x-a)+a^2$ ?and does not intersect? $y=x^2$ ?at any point besides? $P$ . Now for any point? $P$ ?on? $p$ ?let? $P'$ ?be the foot of the perpendicular from? $P$ ?onto? $d$ . Then by the definition of parabolas,? $PP'=PF$ . Let? $q$ ?be the perpendicular bisector of? $overline{P'F}$ . Since? $PP'=PF$ ,? $q$ ?passes through? $P$ . Suppose? $K$ ?is any other point on? $q$ ?and let? $K'$ ?be the foot of the perpendicular from? $K$ ?to? $d$ . Then in right? $Delta KK'P'$ ,? $KK'$ ?is a leg and so? $KK'<KP'=KF$ . Therefore? $K$ ?cannot be on? $p$ . This implies that? $q$ ?is exactly the tangent line to? $p$ ?at? $P$ , that is? $q=ell(P)$ . So we have proved Lemma 1: If? $P$ ?is a point on? $p$ ?then? $ell(P)$ ?is the perpendicular bisector of? $overline{P'F}$ .

We need another lemma before we proceed. Lemma 2: If? $F$ ?is on the circumcircle of? $Delta XYZ$ ?with orthocenter? $H$ , then the reflections of? $F$ across? $overleftrightarrow{XY}$ ,? $overleftrightarrow{XZ}$ , and? $overleftrightarrow{YZ}$ ?are collinear with? $H$ .

Proof of Lemma 2: Say the reflections of? $F$ ?and? $H$ ?across? $overleftrightarrow{YZ}$ ?are? $C'$ ?and? $J$ , and the reflections of? $F$ ?and? $H$ ?across? $overleftrightarrow{XY}$ ?are? $A'$ ?and? $I$ . Then we angle chase? $angle JYZ=angle HYZ=angle HXZ=angle JXZ=m(JZ)/2$ ?where? $m(JZ)$ ?is the measure of minor arc? $JZ$ ?on the circumcircle of? $Delta XYZ$ . This implies that? $J$ ?is on the circumcircle of? $Delta XYZ$ , and similarly? $I$ ?is on the circumcircle of? $Delta XYZ$ . Therefore? $angle C'HJ=angle FJH=m(XF)/2$ , and? $angle A'HX=angle FIX=m(FX)/2$ . So? $angle C'HJ = angle A'HX$ . Since? $J$ ,? $H$ , and? $X$ ?are collinear it follows that? $C'$ ,? $H$ ?and? $A'$ ?are collinear. Similarly, the reflection of? $F$ ?over? $overleftrightarrow{XZ}$ ?also lies on this line, and so the claim is proved.

Now suppose? $A$ ,? $B$ , and? $C$ ?are three points of? $p$ ?and let? $ell(A)capell(B)=X$ ,? $ell(A)capell(C)=Y$ , and? $ell(B)capell(C)=Z$ . Also let? $A''$ ,? $B''$ , and? $C''$ ?be the midpoints of? $overline{A'F}$ ,? $overline{B'F}$ , and? $overline{C'F}$ ?respectively. Then since? $overleftrightarrow{A''B''}parallel overline{A'B'}=d$ ?and? $overleftrightarrow{B''C''}parallel overline{B'C'}=d$ , it follows that? $A''$ ,? $B''$ , and? $C''$ ?are collinear. By Lemma 1, we know that? $A''$ ,? $B''$ , and? $C''$ ?are the feet of the altitudes from? $F$ ?to? $overline{XY}$ ,? $overline{XZ}$ , and? $overline{YZ}$ . Therefore by the Simson Line Theorem,? $F$ ?is on the circumcircle of? $Delta XYZ$ . If? $H$ ?is the orthocenter of? $Delta XYZ$ , then by Lemma 2, it follows that? $H$ ?is on? $overleftrightarrow{A'C'}=d$ . It follows that the locus described in the problem is a subset of? $d$ .

Since we claim that the locus described in the problem is? $d$ , we still need to show that for any choice of? $H$ ?on? $d$ ?there exists an equilateral triangle with center? $H$ ?such that the lines containing the sides of the triangle are tangent to? $p$ . So suppose? $H$ ?is any point on? $d$ ?and let the circle centered at? $H$ ?through? $F$ ?be? $O$ . Then suppose? $A$ ?is one of the intersections of? $d$ ?with? $O$ . Let? $angle HFA=3theta$ , and construct the ray through? $F$ ?on the same halfplane of? $overleftrightarrow{HF}$ ?as? $A$ ?that makes an angle of? $2theta$ ?with? $overleftrightarrow{HF}$ . Say this ray intersects? $O$ ?in a point? $B$ ?besides? $F$ , and let? $q$ be the perpendicular bisector of? $overline{HB}$ . Since? $angle HFB=2theta$ ?and? $angle HFA=3theta$ , we have? $angle BFA=theta$ . By the inscribed angles theorem, it follows that? $angle AHB=2theta$ . Also since? $HF$ ?and? $HB$ ?are both radii,? $Delta HFB$ ?is isosceles and? $angle HBF=angle HFB=2theta$ . Let? $P_1'$ ?be the reflection of? $F$ ?across? $q$ . Then? $2theta=angle FBH=angle C'HB$ , and so? $angle C'HB=angle AHB$ . It follows that? $P_1'$ ?is on? $overleftrightarrow{AH}=d$ , which means? $q$ ?is the perpendicular bisector of? $overline{FP_1'}$ .

Let? $q$ ?intersect? $O$ ?in points? $Y$ ?and? $Z$ ?and let? $X$ ?be the point diametrically opposite to? $B$ ?on? $O$ . Also let? $overline{HB}$ ?intersect? $q$ ?at? $M$ . Then? $HM=HB/2=HZ/2$ . Therefore? $Delta HMZ$ ?is a? $30-60-90$ ?right triangle and so? $angle ZHB=60^{circ}$ . So? $angle ZHY=120^{circ}$ ?and by the inscribed angles theorem,? $angle ZXY=60^{circ}$ . Since? $ZX=ZY$ ?it follows that? $Delta ZXY$ ?is and equilateral triangle with center? $H$ .

By Lemma 2, it follows that the reflections of? $F$ ?across? $overleftrightarrow{XY}$ ?and? $overleftrightarrow{XZ}$ , call them? $P_2'$ ?and? $P_3'$ , lie on? $d$ . Let the intersection of? $overleftrightarrow{YZ}$ ?and the perpendicular to? $d$ ?through? $P_1'$ ?be? $P_1$ , the intersection of? $overleftrightarrow{XY}$ ?and the perpendicular to? $d$ ?through? $P_2'$ ?be? $P_2$ , and the intersection of? $overleftrightarrow{XZ}$ ?and the perpendicular to? $d$ ?through? $P_3'$ ?be? $P_3$ . Then by the definitions of? $P_1'$ ,? $P_2'$ , and? $P_3'$ ?it follows that? $FP_i=P_iP_i'$ ?for? $i=1,2,3$ ?and so? $P_1$ ,? $P_2$ , and? $P_3$ are on? $p$ . By lemma 1,? $ell(P_1)=overleftrightarrow{YZ}$ ,? $ell(P_2)=overleftrightarrow{XY}$ , and? $ell(P_3)=overleftrightarrow{XZ}$ . Therefore the intersections of? $ell(P_1)$ ,? $ell(P_2)$ , and? $ell(P_3)$ ?form an equilateral triangle with center? $H$ , which finishes the proof. --Killbilledtoucan

Solution 2

Note that the lines? $l(P_1), l(P_2), l(P_3)$ ?are $[y=2a_1x-a_1^2, y=2a_2x-a_2^2, y=2a_3x-a_3^2,]$ respectively. It is easy to deduce that the three points of intersection are $[left(frac{a_1+a_2}{2},a_1a_2right),left(frac{a_2+a_3}{2},a_2a_3right), left(frac{a_3+a_1}{2},a_3a_1right).]$ The slopes of each side of this equilateral triangle are $[2a_1,2a_2,2a_3,]$ and we want to find the locus of $[left(frac{a_1+a_2+a_3}{3},frac{a_1a_2+a_2a_3+a_3a_1}{3}right).]$ We know that $[2a_1=tan(theta), 2a_2=tan (theta + 120), 2a_3=tan (theta-120)]$ for some? $theta.$ ?Therefore, we can use the tangent addition formula to deduce $[frac{a_1+a_2+a_3}{3}=frac{tan(theta)+tan (theta + 120)+tan (theta-120)}{6}=frac{3tantheta-tan^3theta}{2-6tan^2theta}]$ and $begin{align*} frac{a_1a_2+a_2a_3+a_3a_1}{3}&=frac{tantheta (tan(theta-120)+tan(theta+120))+tan(theta-120)tan(theta+120)}{12} &=frac{9tan^2theta-3}{12(1-3tan^2theta)} &=-frac{1}{4}.end{align*}$ Now we show that? $frac{a_1+a_2+a_3}{3}$ ?can be any real number. Let's say $[frac{3tantheta-tan^3theta}{2-6tan^2theta}=k]$ for some real number? $k.$ ?Multiplying both sides by? $2-tan^2theta$ ?and rearranging yields a cubic in? $tantheta.$ ?Clearly this cubic has at least one real solution. As? $tan theta$ ?can take on any real number, all values of? $k$ ?are possible, and our answer is the line $[boxed{y=-frac{1}{4}.}]$ Of course, as the denominator could equal 0, we must check? $tan theta=pm frac{1}{sqrt{3}}.$ $[3tan theta-tan^3theta=k(2-6tan^2theta).]$ The left side is nonzero, while the right side is zero, so these values of? $theta$ ?do not contribute to any values of? $k.$ ?So, our answer remains the same.

Problem 4

Solution

Let? $r$ ?be the reflection function on the set of words, namely? $r(a_1dots a_n) = a_n dots a_1$ ?for all words? $a_1 dots a_n$ ,? $nge 1$ . Then the following property is evident (e.g. by mathematical induction):

$r(w_1 dots w_k) = r(w_k) dots r(w_1)$ , for any words? $w_1, dots, w_k$ ,? $k ge 1$ .

a, b, ab, bab, We use mathematical induction to prove the statement of the problem. First,? $W_1 = b$ ,? $W_1W_2 = bab$ ,? $W_1W_2W_3 = babbab$ ?are palindromes. Second, suppose? $nge 3$ , and that the words? $W_1 W_2 dots W_k$ ?( $k = 1$ ,? $2$ ,? $dots$ ,? $n$ ) are all palindromes, i.e.? $r(W_1W_2dots W_k) = W_1W_2dots W_k$ . Now, consider the word? $W_1 W_2 dots W_{n+1}$ :

$[r(W_1 W_2 dots W_{n+1}) = r(W_{n+1}) r(W_1 W_2 dots W_{n-2}W_{n-1}W_n)]$

$[= r(W_{n-1}W_n) W_1 W_2 dots W_{n-2} W_{n-1} W_n]$

$[= r(W_{n-1}W_n) r(W_1 W_2 dots W_{n-2}) W_{n+1}]$

$[= r(W_1 W_2 dots W_{n-2} W_{n-1}W_n) W_{n+1}]$

$[= W_1W_2dots W_n W_{n+1}.]$

By the principle of mathematical induction, the statement of the problem is proved.

Problem 5

Solution 1

Let? $O$ ?be the center of the circle, and let? $X$ ?be the intersection of? $AC$ ?and? $BE$ . Let? $angle OPA$ ?be? $x$ ?and? $angle OPD$ ?be? $y$ .

$angle OPB = angle OPD = y$ ,? $angle BED = frac{angle DOB}{2} = 90-y$ ,? $angle ODE = angle PDE - 90 = 90-x-y$ $angle OBE = angle PBE - 90 = x = angle OPA$

Thus? $PBXO$ ?is a cyclic quadrilateral and? $angle OXP = angle OBP = 90$ ?and so? $X$ ?is the midpoint of chord? $AC$ .

~pandadude

Solution 2

Let? $O$ ?be the center of the circle, and let? $M$ ?be the midpoint of? $AC$ . Let? $theta$ ?denote the circle with diameter? $OP$ . Since? $angle OBP = angle OMP = angle ODP = 90^circ$ ,? $B$ ,? $D$ , and? $M$ ?all lie on? $theta$ .

$[asy] import graph; unitsize(2 cm); pair A, B, C, D, E, M, O, P; path circ; O = (0,0); circ = Circle(O,1); B = dir(100); D = dir(240); P = extension(B, B + rotate(90)*(B), D, D + rotate(90)*(D)); C = dir(-40); A = intersectionpoint((P--(P + 0.9*(C - P))),circ); E = intersectionpoint((D + 0.1*(C - A))--(D + C - A),circ); M = (A + C)/2; draw(circ); draw(P--B); draw(P--D); draw(P--C); draw(B--E); draw(D--E); draw(O--B); draw(O--D); draw(O--M); draw(O--P); draw(Circle((O + P)/2, abs(O - P)/2),dashed); draw(D--M); dot("$A$", A, NE); dot("$B$", B, NE); dot("$C$", C, SE); dot("$D$", D, S); dot("$E$", E, S); dot("$M$", M, NE); dot("$O$", O, dir(0)); dot("$P$", P, W); label("$theta$", (O + P)/2 + abs(O - P)/2*dir(120), NW); [/asy]$

Since quadrilateral? $BOMP$ ?is cyclic,? $angle BMP = angle BOP$ . Triangles? $BOP$ ?and? $DOP$ ?are congruent, so? $angle BOP = angle BOD/2 = angle BED$ , so? $angle BMP = angle BED$ . Because? $AC$ ?and? $DE$ ?are parallel,? $M$ ?lies on? $BE$ ?(using Euclid's Parallel Postulate).

Solution 3

Note that by Lemma 9.9 of EGMO,? $(A,C;B,D)$ ?is a harmonic bundle. We project through? $E$ ?onto? $overline{AC}$ , $[-1=(A,C;B,D)stackrel{E}{=}(A,C;M,P_{infty})]$ Where? $P_{infty}$ ?is the point at infinity for parallel lines? $overline{DE}$ ?and? $overline{AC}$ . Thus, we get? $frac{MA}{MC}=-1$ , and? $M$ ?is the midpoint of? $AC$ .

Solution 4

Connet segment PO, and name the interaction of PO and the circle as point M.

Since PB and PD are tangent to the circle, it's easy to see that M is the midpoint of arc BD.

∠ BOA = 1/2 arc AB + 1/2 arc CE

Since AC // DE, arc AD = arc CE,

thus, ∠ BOA = 1/2 arc AB + 1/2 arc AD = 1/2 arc BD = arc BM = ∠ BOM

Therefore, PBOM is cyclic, ∠ PFO = ∠ OBP = 90°, AF = AC (F is the interaction of BE and AC)

BE bisects AC, proof completed!

Problem 6

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.