Proof. For integers \(x,y\) we write \(x\perp y\) to denote that \(x,y\) are coprime. Let \(s(n)\) denotote the digit sum of \(n\) when written in binary, and \(f(n)\) denote \(\nu_2(n!)\). Without loss of generality, assume \(a\in [0, b).\)

The following relationship between \(s,f\) is well-known: \[f(n) = n-s(n).\]

We break our problem into 3 cases.

Case 0: \(b=1\) This is trivial.

Case 1: \(b\perp 2\).

Then, Euler’s theorem says \(2^{\phi(b)} \equiv 1 \mod b.\) Thus, \[f(2^{\phi(b)}x) = 2^{\phi(b)}x - s(x) \equiv x-s(x) \mod b \equiv f(x).\] Of course, \(f(2) = 1.\) Thus, \[f(\sum_{i=1}^{a} 2^{i\phi(b)}\cdot 2) \equiv a \mod b.\]

Case 2: \(b=2^{k}\).

Then \(f(2^{k}m) \equiv s(m) \mod b.\) So \[f(2^{k}\sum_{i=1}^{a}2^{i}) \equiv a \mod b.\]

Case 3: \(b=c \cdot 2^{k}\) for \(c\perp 2\).

By Case 1, \(\exists n_1\) such that \[f(n_1)\equiv a \mod c.\]

Clearly \(2^{\ell}\bmod 2^{k}c\) cycles through multiples of \(2^{k}\).

Thus, there are integers \(m_1<m_2<\cdots, <m_{\beta c}\) such that \[\forall i, 2^{m_i}\equiv 2^{k}\mod 2^{k}.\] But then \[f(\sum_{i=1}^{\beta c} 2^{m_i}) \equiv \beta c 2^{k} -\beta c \eqquiv -\beta c \mod 2^{k}c.\] In other words, we can get any multiple of \(c\) we want, and we can have an arbirary number of zeros on the right of this number.

Thus, we can nicely compose \(n_1\) with \(f(n_1)\equiv a \mod c\) satisfying \(f(n_1)\equiv a + \beta c \mod 2^{k}c\) with \(n_2\) satisfying \(f(n_2) \equiv -\beta c \mod 2^{k}c\) and \(n_2\) has zeros on all the slots that \(n_1\) would occupy. Therefore, \[f(n_1+n_2)\equiv a \mod 2^{k}c,\] concluding the proof.