Let $v_p(m)$ for a prime p and an integer m be the largest integer d so that $p^d | m$. Prove that for all integers $a$ and $b$ with $b\neq 0,$ there is a positive integer n so that $v_2(n!) \equiv a\mod b.$
I'm not sure how to solve this problem and below is my attempt.
Note that as a consequence of Legendre's formula, we have that for any positive integer m and prime p, $v_p(m!) = (m-s_p(m))/(p-1)$, where $s_p(m)$ is the sum of the digits of n when written in base p. So the problem reduces to showing that there is a positive integer k and positive integers $a_1 < a_2<\cdots < a_k$ so that $2^{a_1} – 1+\cdots + 2^{a_k} – 1\equiv a\mod b$. The $a_i$'s are just the nonzero bits of $n$ when written in base 2. Any positive integer can be written as a sum of distinct powers of 2, which could be useful to know. It could be useful to let $a = 2^{A_1} + \cdots + 2^{A_s}$ be the binary representation of $a$, where $0\leq A_1 < A_2<\cdots < A_s$. As an example, consider $b=5, a=4$. Observe that $2-1 + 2^2 – 1 =4,$ so $v_2(6!)\equiv 4\mod 5$. For $b=8, a=6,$ we consider the numbers $6,14, 22 = 15+7 = 2^4 – 1 + 2^3-1$. So we see that $v_2(24!)\equiv 6\mod 8.$
Best Answer
Suppose $b = 2^t s$, for odd $s$. Let's look at the possible values of $2^a - 1 \pmod b$. According to the CRT, we can look at $2^a - 1 \pmod {2^t}, 2^a - 1 \pmod s$. It's easy to see that it must hit $(-1, 1)$ infinitely many times - $2^a \pmod s$ is periodic, and must hit $2$ infinitely many times, and for all $a \geq t$, $2^a \equiv 0 \pmod {2^t}$. Suppose from CRT we have $(-1, 1) \equiv v \pmod b$. It can be seen that $v^2\equiv 1\pmod b$, so if we use $va\mod b$ copies of $v$, they will sum to $a\pmod b$.
For example, consider $b=24, a=6$. So we have $2^t = 8$, $s = 3$. We have $2^a \equiv 2 \pmod 3 \iff a \equiv 1 \pmod 2$, so $2^3-1, 2^5-1,2^7-1, ...$ all have a value of $(-1, 1) \equiv 7 \pmod {24}$. We can use $7a \equiv 18 \pmod {24}$ such values, so we get $$2^3-1 + 2^5-1 + 2^7-1 + \cdots + 2^{37}-1 \equiv 6 \pmod {24}$$ or $n = 2^3 + 2^5 + \cdots + 2^{37} = 183251937960$.