Problem 1445

1. Initial Setup and Claim:
Let $p$ be a prime number and $a, k$ be positive integers such that $p^a < k < 2p^a$. We need to prove that there exists a positive integer $n$ such that:
$$n < p^{2a}, \quad \binom{n}{k} \equiv n \equiv k \pmod{p^a}.$$
We start by considering two distinct integers $c > c'$ in $\{0, 1, \ldots, p^a - 1\}$. We claim that:
$$\binom{k + cp^a}{k} \not\equiv \binom{k + c'p^a}{k} \pmod{p^a}.$$
Proving this claim will help us establish the desired result.

2. Reduction to a Lemma:
To prove the claim, we first show that if:
$$\binom{z + cp^{a+b}}{k} \not\equiv \binom{z + c'p^{a+b}}{k} \pmod{p^{b+1}},$$
then $c \equiv c' \pmod{p}$ when $z \equiv k \pmod{p^a}$ and $b \le a-1$.

3. Application of Vandermonde Convolution:
Using Vandermonde Convolution, we have:
$$\binom{z + cp^{a+b}}{k} \equiv \binom{z}{k} + \binom{z}{k-p^a} \binom{cp^{a+b}}{p^a} \pmod{p^{b+1}}.$$
Since $\frac{n}{\gcd(m,n)}$ divides $\binom{n}{m}$, and noting that $k - p^a < p^a$, it follows that:
$$\binom{z}{k-p^a} \equiv \binom{k}{k-p^a} \equiv \binom{k}{p^a} \equiv 1 \pmod{p}.$$
This implies that $\binom{z}{k-p^a}$ is a unit modulo $p^{b+1}$, allowing us to cancel it out.

4. Simplifying the Binomial Coefficient:
We need to show:
$$\binom{cp^{a+b}}{p^a} \equiv \binom{c'p^{a+b}}{p^a} \pmod{p^{b+1}}.$$
This reduces to:
$$\frac{cp^{a+b}}{p^a} \binom{cp^{a+b}-1}{p^a-1} \equiv \frac{c'p^{a+b}}{p^a} \binom{c'p^{a+b}-1}{p^a-1} \pmod{p^{b+1}}.$$
Simplifying further, we get:
$$c \binom{cp^{a+b}-1}{p^a-1} \equiv c' \binom{c'p^{a+b}-1}{p^a-1} \pmod{p}.$$
Since $\binom{cp^{a+b}-1}{p^a-1}$ and $\binom{c'p^{a+b}-1}{p^a-1}$ are units modulo $p$, we conclude:
$$c \equiv c' \pmod{p}.$$

5. Inductive Argument:
Suppose $\binom{k + cp^a}{k} \equiv \binom{k + c'p^a}{k} \pmod{p^a}$. By the lemma with $b = 0$, we have $c \equiv c' \pmod{p}$. Let $c = c_1 + a_1p$ and $c' = c'_1 + a'_1p$. By the lemma again, $a_1 \equiv a_1' \pmod{p}$, so $c \equiv c' \pmod{p^2}$. Continuing this process, we find $c \equiv c' \pmod{p^a}$, which is a contradiction if $c$ and $c'$ are distinct.

6. Conclusion:
Therefore, the numbers of the form $\binom{k + cp^a}{k}$ for $c = 0, 1, \ldots, p^a$ must cover all residues modulo $p^a$. This implies the existence of a positive integer $n$ such that:
$$n < p^{2a}, \quad \binom{n}{k} \equiv n \equiv k \pmod{p^a}.$$

$\blacksquare$