MathLabs

Problem 6

Find all positive integers nn for which there exist nonnegative integers a1,…,ana_1,\dots,a_n such that ∑i=1n2−ai=∑i=1ni3−ai=1\sum_{i=1}^n2^{-a_i}=\sum_{i=1}^n i3^{-a_i}=1.
Step 1 of 4: Derive the necessary congruence
Previous stepNext step
In plain words

Clearing the largest power of 3 turns the second equality into an integer congruence modulo n.

3M=∑i=1ni3M−ai≡n(n+1)2≡1(mod2)3^M=\sum_{i=1}^n i3^{M-a_i}\equiv\frac{n(n+1)}2\equiv1\pmod2
Detailed analysis

Let M=max⁡iaiM=\max_i a_i. Multiplying ∑i=1ni3−ai=1\sum_{i=1}^n i3^{-a_i}=1 by 3M3^M gives 3M=∑ii3M−ai3^M=\sum_i i3^{M-a_i}. Reducing this integer equality modulo 2, the left side is odd and the right side is congruent to 1+2+⋯+n=n(n+1)/21+2+\cdots+n=n(n+1)/2. Hence this triangular number is odd, so n≡1,2(mod4)n\equiv1,2\pmod4.