uniformity of combination

Question

Let $m>1$, $n$, $k$ be positive integers. Does there exist a positive integer $l>m-1$ such that $\binom{l}{m} \equiv k \pmod{2^n}$? I see it at princeton companion to mathematics.

Answer 1

Let $\nu_2$ denote the $2$-adic valuation.

Lemma For every $m>1$ there exists $u$ such that

1. $1\leq u\leq m$;
2. $\nu_2(u)\geq\nu_2(v)$ for every $1\leq v\leq m$;
3. if $1\leq v\leq m$ and $\nu_2(u)=\nu_2(v)$ then $v=u$.

proof. Clearly there exists $u$ satisfying (1) and (2). To prove (3) assume $1\leq u<v\leq m$ such that $\nu_2(u)=\nu_2(v)$. Then $1\leq v-u\leq m$ and $\nu_2(v-u)>\nu_2(u)$ - a contradiction.

Now let $m$ and $u$ as in the lemma. Then \begin{align} p(x) &=\binom{2^ux-1}m\\ &=\frac 1{m!}\prod_{v=1}^m(2^ux-v)\\ &=\frac{2^{\nu_2(m!)}}{m!}\prod_{v=1}^m(2^{u-\nu_2(v)}x-2^{-\nu_2(v)}v)\\ &=\frac 1d\prod_{v=1}^m(2^{u-\nu_2(v)}x-d_v) \end{align} where $d$ and $d_v$ are odd numbers satisfying $m!=2^{\nu_2(m!)}d$ and $v=2^{\nu_2(v)}d_v$. Consequently, $p$ is a polynomial with coefficients in $\Bbb{\hat Z}_2$, the ring of $2$-adic integers. Moreover $p(x)\equiv x-d_u\pmod 2$, hence the equation $p(x)\equiv k\pmod 2$ has a solution for every $k$. Moreover, $$p'(x)\equiv 1\pmod 2$$ hence the equation $p(x)\equiv k\pmod 2$ has simple roots. By Hensel's lemma, the simple root of $p(x)\equiv k\pmod 2$ can be lifted to a root of $p(x)=k$ in $\Bbb{\hat Z}_2$. Consequently, the congruence $\binom lm\equiv k\pmod{2^n}$ has solution for every $n>0$.