Summer Problem Solving Marathon Solution #33

For any choice of n, we can write 2ⁿ in the form nk + m, for some k and some m < n. (That is, we write 2ⁿ as some multiple of n, plus a remainder on division by n.)

We then rewrite 2⁽²ⁿ⁾ as 2^{nk + m} = 2^nk2^m.

We are now interested in the remainder of this when divided by 2ⁿ - 1. Since m < n, the remainder of 2^m when divided by 2ⁿ -1 is 2^m. 2^nk can be rewritten as (2ⁿ)^k. But the remainder of 2ⁿ when divided by 2ⁿ -1 is clearly 1, so the remainder of (2ⁿ)^k when divided by 2ⁿ -1 is 1^k = 1.

Thus the remainder of 2⁽²ⁿ⁾ when divided by 2ⁿ -1 is 2^m. We want the remainder not to be a power of 4, which means we want m to be odd.

We are thus looking for n such that 2ⁿ, when divided by n, produces an odd remainder. Examination of cases then shows that 25 is the first value of n that works.