Problem 1625

To prove that $\binom{n \cdot p^k}{p^k}$ and $p$ are coprime, we need to show that the $p$-adic valuation of $\binom{n \cdot p^k}{p^k}$ is zero, i.e., $v_p \left( \binom{n \cdot p^k}{p^k} \right) = 0$.

1. **Definition and Properties of $v_p$**:
Let $v_p(n)$ denote the exponent of $p$ in the prime factorization of $n$. For any natural numbers $a$ and $b$, the following properties hold:
$$v_p(ab) = v_p(a) + v_p(b) \quad \text{and} \quad v_p\left(\frac{a}{b}\right) = v_p(a) - v_p(b)$$
Additionally, for any natural number $n$:
$$v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$$

2. **Expression for $v_p \left( \binom{n \cdot p^k}{p^k} \right)$**:
We start with the binomial coefficient:
$$\binom{n \cdot p^k}{p^k} = \frac{(n \cdot p^k)!}{(p^k)! \cdot ((n-1) \cdot p^k)!}$$
Taking the $p$-adic valuation, we get:
$$v_p \left( \binom{n \cdot p^k}{p^k} \right) = v_p \left( (n \cdot p^k)! \right) - v_p \left( (p^k)! \right) - v_p \left( ((n-1) \cdot p^k)! \right)$$

3. **Calculating $v_p \left( (n \cdot p^k)! \right)$**:
Using the formula for $v_p(n!)$:
$$v_p \left( (n \cdot p^k)! \right) = \sum_{i=1}^{\infty} \left\lfloor \frac{n \cdot p^k}{p^i} \right\rfloor = \sum_{i=1}^{\infty} \left\lfloor \frac{n \cdot p^k}{p^i} \right\rfloor = \sum_{i=1}^{\infty} \left\lfloor n \cdot p^{k-i} \right\rfloor$$

4. **Calculating $v_p \left( (p^k)! \right)$**:
$$v_p \left( (p^k)! \right) = \sum_{i=1}^{\infty} \left\lfloor \frac{p^k}{p^i} \right\rfloor = \sum_{i=1}^{k} \left\lfloor p^{k-i} \right\rfloor = p^{k-1} + p^{k-2} + \cdots + p + 1$$

5. **Calculating $v_p \left( ((n-1) \cdot p^k)! \right)$**:
$$v_p \left( ((n-1) \cdot p^k)! \right) = \sum_{i=1}^{\infty} \left\lfloor \frac{(n-1) \cdot p^k}{p^i} \right\rfloor = \sum_{i=1}^{\infty} \left\lfloor (n-1) \cdot p^{k-i} \right\rfloor$$

6. Combining the Results:
$$v_p \left( \binom{n \cdot p^k}{p^k} \right) = \sum_{i=1}^{\infty} \left\lfloor n \cdot p^{k-i} \right\rfloor - \left( \sum_{i=1}^{k} p^{k-i} \right) - \sum_{i=1}^{\infty} \left\lfloor (n-1) \cdot p^{k-i} \right\rfloor$$
Simplifying, we get:
$$v_p \left( \binom{n \cdot p^k}{p^k} \right) = \sum_{i=1}^{\infty} \left( \left\lfloor n \cdot p^{k-i} \right\rfloor - \left\lfloor (n-1) \cdot p^{k-i} \right\rfloor \right) - \left( p^{k-1} + p^{k-2} + \cdots + p + 1 \right) + \left( p^{k-1} + p^{k-2} + \cdots + p + 1 \right)$$
Since $\gcd(n, p) = 1$, $n$ is not divisible by $p$, and thus:
$$\left\lfloor \frac{n}{p^i} \right\rfloor = \left\lfloor \frac{n-1}{p^i} \right\rfloor$$
Therefore:
$$v_p \left( \binom{n \cdot p^k}{p^k} \right) = 0$$

Since $v_p \left( \binom{n \cdot p^k}{p^k} \right) = 0$, it follows that $\binom{n \cdot p^k}{p^k}$ and $p$ are coprime.

$\blacksquare$