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(\mathrm{mod}{p}^a)$ and $C_n^k\equiv k(\mathrm{mod}{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(\mathrm{mod}{p}^a)$, and $C_n^k\equiv k(\mathrm{mod}{p}^b)$.

Let $1\le t\le p-1$. Consider $$C_{n+t{p}^{a+b}}^k=\prod _{i=0}^{k-1}\frac{n+t{p}^{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(\mathrm{mod}{p}^a)$. Hence, $$P(k-i)\mid n+t{p}^{a+b}-i.$$ Consequently, $$C_{n+t{p}^{a+b}}^k=\prod _{i=0}^{k-1}\frac{\frac{n-i}{P(k-i)}+t{p}^{a+b-v_p(k-i)}}{r(k-i)}.$$ If $k-i\ne p^a$, then $v_p(k-i)⩽a-1$ and $a+b-v_p(k-i)⩾b+1$. If $k-i=p^a$, then $v_p(k-i)=a$. Hence, $$\begin{gathered} C_{n+t{p}^{a+b}}^k\equiv \prod _{i=0}^{k-1}\frac{n-i}{P(k-i)r(k-i)}+\left(\prod _{\begin{array}{c}0\le i\le k-1\\ i\ne k-p^a\end{array}}^{k-1}\frac{n-i}{P(k-i)r(k-i)}\right)\cdot t{p}^b \\ \equiv C_n^k+\left(\prod _{\begin{array}{c}0\le i\le k-1\\ i\ne k-p^a\end{array}}^{k-1}\frac{r(n-i)}{r(k-i)}\right)\cdot t{p}^b(\mathrm{mod}{p}^{b+1}). \end{gathered}$$ This is because that if $k-i\ne p^a$, then $p^a\mid (n-i)-(k-i)$. So $$v_p(n-i)=v_p(k-i).$$ Since ${\prod }_{\begin{array}{c}0\le i\le k-1\\ i\ne k-p^a\end{array}}\frac{r(n-i)}{r(k-i)}$ is coprime to $p$, we see that $C_{n+t{p}^{a+b}}^k$ ($0\le t\le p-1$) goes through the following remainders modulo $p^{b+1}$: $$C_n^k+j{p}^b,j=0,1,\dots ,p-1.$$ Since $C_n^k\equiv k(\mathrm{mod}{p}^b)$, there exists $j$ ($0\le j\le p-1$), such that $C_n^k+j{p}^b\equiv k(\mathrm{mod}{p}^{b+1})$. That is, there exists $t$ ($0\le t\le p-1$), such that $C_{n+t{p}^{a+b}}^k\equiv k(\mathrm{mod}{p}^{b+1})$. Let $N=n+t{p}^{a+b}$. Then $N<p^{a+b+1}$, $N\equiv n\equiv k(\mathrm{mod}{p}^a)$ and $C_N^k\equiv k(\mathrm{mod}{p}^{b+1})$.

The extended problem is proved by induction. ☐