Er no time to write out a proof right now, but counterexample of $n=25$ works beautifully.

Was there any special reason why 25 works or was it just guess and check? I spent 4 hours trying to prove that the problem statement is true

clearly 2^n == 1 (mod 2^n - 1). Let 2^n == r mod n where 0<= r < n. then 2^2^n == 2^r mod 2^n - 1. with primes 2^p == 2 mod n, so that gives power of 4, and evens clearly give power of 4. you check a few and then you get to 25

I used the counterexample n = 123455, it worked really well.

i actually did 225 first just because it wasn't too hard to get at. i also didn't think that 25 would be a counterexample until i realized it 2 minutes after i finished writing up 225. oh well.

cwein3 wrote: Was there any special reason why 25 works or was it just guess and check? By the method in Yongyi781's solution, if the remainder when dividing $2^n$ by $n$ is odd, then the remainder when dividing $2^{2^n}$ by $2^n-1$ is not a multiple of 4. Clearly the remainder (which I'll call $r$) when dividing $2^n$ by $n$ is even when $n$ is even, and it can be shown that when $n$ is a multiple of three $r=8$. Also, when $n$ is prime $2^n\equiv2\pmod n$ by Fermat's little theorem. Thus, the only possible counterexamples are relatively prime to 2 and 3, and are composite. 25 is the smallest such number. (I didn't notice that the factors could be the same, and since 35 yields an even remainder, I thought 55 was the smallest counterexample.)

Hm why does there seem to be a lot of constructive problems this year as closers (e.g. last problem of BAMO12 and USAMTS) Anyways, I used $n=91$. I just guessed that because it was a semiprime with two somewhat large primes and it happened to work.

Did you have to give a full set of all solutions that didn't work? I just started my solution with "Let n=25" and showed that it made everything failed.

@above, nope, one counterexample should be sufficient. We're just discussing.

I epic failed this one. Can anyone tell me what's wrong with this? We are looking for $2^{2^{n}} \pmod {2^n -1}$. $2^{2^{n}} \equiv 2^{2^{n}} - (2^n - 1)\cdot 2^{2^n - n} \equiv 2^{2^n -n} \pmod {2^n -1}$ $2^{2^n - n} \equiv 2^{2^n -n} - (2^n -1) \cdot 2^{2^n - 2n} \equiv 2^{2^n - 2n} \pmod {2^n -1}$. So the remainder is $2^{2^n - 2n} = 4^{2^{n-1} - n}$, so that is a perfect power of 4.

I actually had no idea if there was a counterexample or not. I wrote up almost all of the solution without mentioning whether the assertion was true or not with 20 minutes left. When I couldn't prove it, I frantically tried random odd non-prime numbers until I got 25 with about a minute left. @hrithikguy you need to show that $2^{2^n-2n}<2^n-1$ for it to be the remainder.

Because who says that $4^{2^{n-1}-n}$ is less than $2^n-1$? In fact, that is only true a finite number of times, probably 1. I'm too lazy to check.

cwein3 wrote: Was there any special reason why 25 works or was it just guess and check? I spent 4 hours trying to prove that the problem statement is true I used guess and check, but not before plowing through this:

Took me 30 minutes, which is better than I can say for the last time I did the USAMO

The first 45 minutes was spent doing this (you'll laugh):

The next 45 minutes was actually reducing the problem and solving it. This will make stevenmeow happy.

Oh whoops I failed this one really badly. 0/7 then.

MathWise wrote: Clearly the remainder (which I'll call $r$) when dividing $2^n$ by $n$ is even when $n$ is even, and it can be shown that when $n$ is a multiple of three $r=8$. Hmm Image not found

How many points, if any, do you guys think it'd be worth for proving that the problem statement was equivalent to showing if 2^n mod n was even, and then proving it for primes/even numbers?

cwein3 wrote: Was there any special reason why 25 works or was it just guess and check? I spent 4 hours trying to prove that the problem statement is true Same here.

v_Enhance wrote: Haha, by "guess randomly" I meant guess non-primes randomly. Not that I did so, I random-guessed until I hit 91 which worked. is there a way to not random guess?(like random guessing non-primes) Or is there a way to random guess more easily? Because I just randomly guessed till 18 and tried to prove that there are no existing numbers that satisfy (I used 2 hours to solve this )

I got 25 as counterexample and cannot remember how I got it when I did the qn 1 yr ago. Full proof here (it is constructive) https://infinityintegral.substack.com/p/usajmo-2011-contest-review

bruh this should be some aime problem oly problems should not be bash The order of 2 mod 2^n-1 is n, so $$2^{2^n}\equiv 2^{2^n \pmod n}\pmod {2^n -1}.$$Hence if we can get $2^n\pmod n$ to be odd then it would be an odd power of 2, which is not a power of 4. It's now incredibly quick and easy to bash to find a counterexample by noting that n is odd (otherwise reduced modulo is always even) and that $2^{n\pmod {\phi(n)}}$ must be greater than n (otherwise the remainder is the same as the power of 2, meaning it's not odd). Indeed, n=25 does the job. $\blacksquare$ (Note: If this did not work for small n we would be out of luck, oops)

Can't you do proof by contradiction for this one?

aarushgoradia18 wrote: Can't you do proof by contradiction for this one? Yes, that is pretty much what the question is asking for..

$2^{2^n-n}(2^n-1)+2^{2^n-n}=2^{2^n}-2^{2^n-n}+2^{2^n-n}=2^{2^n}$ So the remainder is equal to $2^{2^n-n}$ mod $2^n-1$. Repeat this to get that the remainder is $2^{2^n \pmod n}$ If the remainder is not a power of $4$, $2^n \pmod n$ is odd. If $n$ is prime, then $2^n \equiv 2 \pmod n$, which is even. $n$ also has to be odd because an the remainder when an even is divided by an even is an even. Testing the composite odd numbers $9,15,21,25$ results in $25$ working

This took me far longer than it should've. I claim that $2^{2^n}$ does not always leave a remainder that is a power of $4$ upon division by $2^n - 1$. Observe that \[2^{2^n} \equiv 2^{2^n - n} \equiv \cdots 2^{2^n - kn} \pmod{2^n - 1},\]where $2^n = kn + \ell$. Now in order for $2^{2^n}$ to not be a power of $4$, we require $\ell$ to be odd. Therefore we must find some $n$ for which $2^n \equiv \ell \pmod n$, where $\ell$ just so happens to be odd. Now first observe $2^p \equiv 2 \pmod p$, so all primes are excluded, and further, even powers result in even remainders. Hence $n$ must be the product of more than two not necessarily distinct odd primes. So the first few values of $n$ may be $n = 9, 15, 21, 25, 27, 33, 35, 39, 45,...$ however simply checking yields that $2^{25} \equiv 7 \pmod{25}$, providing the counterexample of $\boxed{n = 25}$. $\blacksquare$

we can see that $2^{2^n}$ divided by $2^n-1$ gives $2^{{2^n}-n-n-n-n-n \cdots}$, aka $2^{{2^n}\mod(n)}$ thus, finding a counterexample is equivalent to finding an ${2^n}\mod(n)$ that is odd that is then equivalent to finding an ${2^d(n)}\mod(n)$ that is odd, where $d(n)$ is the amount of numbers less than or equal to $n$ and not relatively prime to $n$ it is clear that any even $n$ or $d(n)$ do not work, so we plug in odd perfect squares it is clear $n=9$ gives ${8}\mod(9)$, which does not work, but $n=25$ gives ${32}\mod(25) \equiv {7}\mod(25)$, which works thus we have a counterexample and solved this problem

The idea is to restrict possible values of $n$. Note that we have $2^{2^n} \equiv 2^{2^n \bmod n} \pmod {2^n - 1}$. For this remainder not to be a power of $4$, $2^n \bmod n$ must be odd. This immediately implies that $n$ must be an odd composite number, for which checking the first few values yields $n=25$ works ($2^{25} \bmod {25} = 7$).

We provide a counter example when $n=25$. Note that $2^n\equiv 1\pmod{2^n-1}$. Therefore, if $2^n\equiv a\pmod{n}$, then: \[2^{2^n}\equiv 2^a\pmod{2^n-1}.\]It then suffices to show $a$ is odd. If $a$ is prime, by FLT, $2^n\equiv 2\pmod{n}$, so it fails. If $a=p^2$, for a prime $p$, then by Euler's formula: \[2^{p^2}\equiv 2^p\pmod{p^2}.\]We can check $p=3$, and it results in $a$ even. If $p=5$, then it results in $a=7$, which is odd, so we are done $\blacksquare$

Usernumbersomething wrote: Do counterexamples to this have positive natural density? Can someone try to answer this? I only know of empirical results. OEIS has no pointers

Bumping this because I feel it's an interesting question.

I claim that $n=25$ doesn't work. Note that \[2^{25}\equiv 1 \mod (2^{25}-1),\]and that by Euler's Totient, we have that \[2^{20}\equiv 1\mod 25.\]Using this, note that \[2^{25}\equiv 2^5\equiv 7\mod 25,\]meaning that \[2^{2^{25}}\equiv 2^7 \equiv 32\mod (2^{25}-1),\]which is indeed not a power of $4$, finishing the problem.

The assertion is false. Let $k = 2^{25} \bmod 25 = 7$. Now \[2^{2^{25}} \equiv 2^{25 + 25 + \dots + 25 + k} \equiv 2^{25} \cdot 2^{25} \cdot \dots \cdot 2^{25} \cdot 2^k \equiv 2^k \equiv 2^7 \pmod{2^{25} - 1}\]and we're done since $2^7$ is obviously the remainder.