China Mathematical Olympiad

For each positive integer $n$, we write $n$ in binary representation as $n=2^{a_1}+2^{a_2}+\cdots +2^{a_k}$, where $0\le a_1<a_2<\cdots <a_k$. Define a set $T(n)=\{2^{a_1},\dots ,2^{a_k}\}$, $T(0)$ is considered empty set. By Lucas' theorem, $C_n^i$ is odd if and only if $T(i)\le T(n)$, hence $$f(n,q)=\sum _{A\subseteq T(n)}{q}^{\sigma (A)}=\prod _{a\in T(n)}(1+q^a),$$ where $\sigma (A)$ denotes the sum of all elements of $A$. For $m,n$ and $q$ as given by assumption, we show that if $$f(m,q)=\prod _{a\in T(m)}(1+q^a)\mid \prod _{a\in T(n)}(1+q^a)=f(n,q),$$ then $T(m)\subseteq T(n)$, and consequently, $f(m,r)\mid f(n,r)$ for every $r$. For any integers $i,j$, $0\le i<j$, we have the following factorization: $$q^{2j}-1=(q^{2j-1}+1)\cdots (q^2+1)(q^2-1),$$ therefore $$(q^{2j}+1,q^{2i}+1)=(q^{2i}+1,2)\mid 2.$$ Let $s(k)$ be the largest odd divisor of a positive integer $k$, then it follows that $s(q^{2i}+1)$ and $s(q^{2j}+1)$ are coprime. Clearly $q>1$. If $i>0$, $q^{2i}+1\equiv 1(\mathrm{mod}2)$, and $q^{2j}+1>2$, thus $s(q^{2i}+1)>1$. If $i=0$, since $q+1$ is not a power of $2$, we have $s(q+1)>1$. For any $a\in T(m)$, $s(q^a+1)\mid {\prod }_{b\in T(n)}s(q^b+1)$. Since $s(1+q^a)>1$, we have $a\in T(n)$, hence $T(m)\subseteq T(n)$, which completes the proof!