China National Team Selection Test

Let $p$ be a prime, $a$ and $k$ be positive integers, satisfying $p^a < k < 2p^a$. Prove that for any non-negative integer $b$, there exists positive integer $n$, $n < p^{a+b}$ such that $n \equiv k \pmod{p^a}$ and $C_n^k \equiv k \pmod{p^b}$.

If $b=0$, $p^b = 1$, take $n = k - p^a$. We prove by induction. Suppose that the conclusion is true for integer $b \ge 0$. That is, there exists a positive integer $n < p^{a+b}$, $n \equiv k \pmod{p^a}$, and $C_n^k \equiv k \pmod{p^b}$.

Let $1 \le t \le p-1$. Consider
$$C_{n+tp^{a+b}}^{k} = \prod_{i=0}^{k-1} \frac{n + tp^{a+b} - i}{k-i}.$$
For integer $m$, let $P(m) = p^{v_p(m)}$, $r(m) = \frac{m}{P(m)}$, where $v_p(m)$ is the number of $p$ in the standard factorization of $m$.

Since $k - i < 2p^a \le p^{a+1}$, we see that $v_p(k-i) \le a$ and $n - i \equiv k - i \pmod{p^a}$. Hence,
$$P(k-i) \mid n + tp^{a+b} - i.$$
Consequently,
$$C_{n+tp^{a+b}}^{k} = \prod_{i=0}^{k-1} \frac{\frac{n-i}{P(k-i)} + tp^{a+b-v_p(k-i)}}{r(k-i)}.$$
If $k - i \neq p^a$, then $v_p(k - i) \leqslant a - 1$ and $a + b - v_p(k - i) \geqslant b + 1$. If $k - i = p^a$, then $v_p(k - i) = a$. Hence,
$$C_{n+tp^{a+b}}^{k} \equiv \prod_{i=0}^{k-1} \frac{n-i}{P(k-i)r(k-i)} + \left( \prod_{\substack{0 \le i \le k-1 \\ i \ne k-p^a}}^{k-1} \frac{n-i}{P(k-i)r(k-i)} \right) \cdot tp^b \\ \equiv C_n^k + \left( \prod_{\substack{0 \le i \le k-1 \\ i \ne k-p^a}}^{k-1} \frac{r(n-i)}{r(k-i)} \right) \cdot tp^b \pmod{p^{b+1}}.$$
This is because that if $k - i \neq p^a$, then $p^a \mid (n - i) - (k - i)$. So
$$v_p(n-i) = v_p(k-i).$$
Since $\prod_{\substack{0 \le i \le k-1 \\ i \ne k-p^a}} \frac{r(n-i)}{r(k-i)}$ is coprime to $p$, we see that $C_{n+tp^{a+b}}^k$ ($0 \le t \le p-1$) goes through the following remainders modulo $p^{b+1}$:
$$C_n^k + j p^b, \quad j = 0, 1, \dots, p-1.$$
Since $C_n^k \equiv k \pmod{p^b}$, there exists $j$ ($0 \le j \le p-1$), such that $C_n^k + j p^b \equiv k \pmod{p^{b+1}}$. That is, there exists $t$ ($0 \le t \le p-1$), such that $C_{n+tp^{a+b}}^k \equiv k \pmod{p^{b+1}}$. Let $N = n + tp^{a+b}$. Then $N < p^{a+b+1}$, $N \equiv n \equiv k \pmod{p^a}$ and $C_N^k \equiv k \pmod{p^{b+1}}$.

The extended problem is proved by induction. ☐