For any positive integer $n$ and $0 \leqslant i \leqslant n$, denote $C_n^i \equiv c(n,i)\pmod{2}$, where $c(n,i) \in \left\{ {0,1} \right\}$. Define \[f(n,q) = \sum\limits_{i = 0}^n {c(n,i){q^i}}\] where $m,n,q$ are positive integers and $q + 1 \ne {2^\alpha }$ for any $\alpha \in \mathbb N$. Prove that if $f(m,q)\left| {f(n,q)} \right.$, then $f(m,r)\left| {f(n,r)} \right.$ for any positive integer $r$.
Problem
Source: 2013 China Mathematical Olympaid P5
Tags: modular arithmetic, algebra, polynomial, function, number theory proposed, number theory
14.01.2013 06:55
Consider the polynomial $f(n,x) = \sum\limits_{i = 0}^n{c(n,i){x^i}}$ where the binary representation of $n$ is $n = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_k}$ where $0 \le a_1<a_2<\cdots < a_k$. By definition, it follows that $f(n,x) \equiv (1+x)^n \pmod{2}$. Now examine the product $(1+x^{2^{a_1}})(1+x^{2^{a_2}})\cdots (1+ x^{2^{a_k}})$. Now note that for each nonnegative integer $i$, it follows that ${1+x^{2^i}} \equiv (1+ x)^{2^{i}} \pmod{2}$. Therefore the product above is congruent to $(1+x)^n$ in modulo $2$ and therefore to $f(n,x)$. Viewing the product as a generating function of $x$ yields that the coefficients of the expansion are each either $0$ or equal to $1$ if the corresponding term $x^i$ satisfies that $i$ has binary digits in a set of positions that are a subset of $\{ a_1, a_2, \dots, a_k \}$. Therefore the coefficients of this product are each either $0$ or $1$ which implies that the product is equal to $f(n,x)$. Now consider $f(m,q)$ and $f(n,q)$. By the given condition, $q \ge 2$. As shown above, each can be expressed as the product of terms of the form $1+q^{2^j}$. For any two distinct such terms, reducing the larger one modulo the smaller one yields that their greatest common divisor divides $2$. If $j= 0$, then as given, $1+ q$ is not a power of $2$ and thus has an odd prime divisor $p$. Similarly, if $j \ge 1$, then $1 + q^{2^j} \equiv 1, 2 \pmod{4}$ and thus, since $q \ge 2$, must have an odd prime divisor $p$ as well. Thus if any such term in the product representation of $f(m,q)$ does not appear in the representation of $f(n,q)$, it has an odd prime divisor $p$ that cannot divide any term in the product representation of $f(n,q)$ (since the greatest common divisor of any two terms divides $2$). This is a contradiction and, by examining the formula for $f(n,x)$ shown above, implies that every digit in the binary representation of $m$ also appears in the binary representation of $n$. By this same formula, it follows that $f(m,r)$ divides $f(n,r)$ for all positive integers $r$.
16.01.2013 14:58
They are basically same : http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2668065#p2668065
18.03.2022 09:10
The key observation is that if $n=2^{d_1}+2^{d_2}+\cdots+2^{d_k}$ where $d_1>d_2>\cdots>d_k$ then $f(n,x)=\prod\limits_{j=1}^k (1+x^{2^{d_j}})$ Assume $f(m,q)\mid f(n,q)$ where $q+1$ is not a power of 2. I claim if $m$ has $2^l$-bit ON in its binary representation, then so must $n$. Induct on $m$. If $m$ is even then note $f(m,q)=f(\frac m2, q^2)$, so we assume $m$ is odd. This means $q+1\mid f(m,q)$. Assume for contradiction $n$ is even. This means $q+1\mid f(n,q)=\prod\limits_{j=1}^k (1+q^{2^{d_j}})$. Since $d_j>0$ for all $j$, $1+q^{2^{d_j}}\equiv 2(\bmod\; q+1)$ so $q+1\mid 2^k$, contradicting the assumption that $q+1$ is not a power of 2. The key observation is that if $n=2^{d_1}+2^{d_2}+\cdots+2^{d_k}$ where $d_1>d_2>\cdots>d_k$ then $f(n,x)=\prod\limits_{j=1}^k (1+x^{2^{d_j}})$ Assume $f(m,q)\mid f(n,q)$ where $q+1$ is not a power of 2. I claim if $m$ has $2^l$-bit ON in its binary representation, then so must $n$. Induct on $m$. Consider the smallest bit that is on, call $2^t$. This means $f(m,q)$ is divisible by $1+q^{2^t}$. Assume for contradiction that $n$ doesn't have it on. Let $p$ be an odd prime divisor of $1+q^{2^t}$, which exists since it is not a power of 2. For bits larger than $d$: $1+q^{2^l} \equiv 2(\bmod\; 1+q^{2^l})$ for any $l>d$ so $p\nmid 1+q^{2^l}$ if $l>d$ For bits smaller than $d$: $1+q^{2^t}\equiv 2(\bmod\; 1+q^{2^l})$ for any $l<d$ so $p\nmid 1+q^{2^l}$ if $l<d$ It follows that $n$ must have this bit on. Now consider $(m-2^d,n-2^d)$ and induct down.