Problem 1406

1. Lemma: We start by proving the lemma that $X_{\alpha} \equiv X_{\alpha + 1} \pmod{p^{\alpha + 1}}$, where $p$ is a prime and $X_{\alpha} = \binom{dp^{\alpha}q - 1}{dp^{\alpha} - 1}$.

2. Define $f(x) = (x - 1)(x - 2) \cdots (x - p + 1)$, where $p$ is a prime.

3. Using the definition of the binomial coefficient, expand $X_{\alpha}$ and $X_{\alpha + 1}$:
$$X_{\alpha + 1} - X_{\alpha} = X_{\alpha} \left( \frac{f(dp^{\alpha + 1}q) f(dp^{\alpha + 1}q - p) \cdots f(dp^{\alpha + 1}q - dp^{\alpha + 1} + p)}{f(dp^{\alpha + 1}) f(dp^{\alpha + 1} - p) \cdots f(p)} - 1 \right)$$

4. Note that $f(kp)$ is not a multiple of $p$.

5. We need to show:
$$f(dp^{\alpha + 1}q) f(dp^{\alpha + 1}q - p) \cdots f(dp^{\alpha + 1}q - dp^{\alpha + 1} + p) \equiv f(dp^{\alpha + 1}) f(dp^{\alpha + 1} - p) \cdots f(p) \pmod{p^{\alpha + 1}}$$

6. This is obvious because $f(dp^{\alpha + 1}q - kp) \equiv f(dp^{\alpha + 1} - kp) \pmod{p^{\alpha + 1}}$ for any integer $k$.

7. This completes the proof of our lemma.

8. Main Problem: We need to prove that the sum of binomial coefficients:
$$\sum_{k=0}^{n-1} \binom{\gcd(n, k)q}{\gcd(n, k)}$$
is divisible by $m$.

9. It is equivalent to:
$$n \mid \sum_{d \mid n} \binom{dq - 1}{d - 1} \phi\left(\frac{n}{d}\right)$$

10. Denote $n = p^{\alpha}m$ where $(m, p) = 1$. We need to show:
$$p^{\alpha} \mid \sum_{d \mid m} \sum_{k=0}^{\alpha} \binom{dp^kq - 1}{dp^k - 1} \phi\left(\frac{p^{\alpha - k}m}{d}\right)$$

11. We need to show $p^{\alpha} \mid A_{\alpha}$, where:
$$A_{\alpha} = \sum_{k=0}^{\alpha} \binom{dp^kq - 1}{dp^k - 1} \phi\left(\frac{p^{\alpha - k}m}{d}\right)$$

12. Use induction on $\alpha$.

13. Note that:
$$A_{\alpha + 1} = \sum_{k=0}^{\alpha + 1} \binom{dp^kq - 1}{dp^k - 1} \phi\left(\frac{p^{\alpha + 1 - k}m}{d}\right)$$

14. Using properties of Euler's totient function:
$$\phi\left(\frac{mp}{d}\right) = (p - 1) \phi\left(\frac{m}{d}\right), \quad \phi\left(\frac{mp^a}{d}\right) = p \phi\left(\frac{m^{a - 1}}{d}\right) \text{ for } a > 1$$

15. We get:
$$A_{\alpha + 1} = pA_{\alpha} + \binom{dqp^{\alpha + 1} - 1}{dp^{\alpha + 1} - 1} \phi\left(\frac{m}{d}\right) - \binom{dqp^{\alpha} - 1}{dp^{\alpha} - 1} \phi\left(\frac{m}{d}\right)$$

16. Thus:
$$A_{\alpha + 1} \equiv \phi\left(\frac{m}{d}\right) \left( \binom{dqp^{\alpha + 1} - 1}{dp^{\alpha + 1} - 1} - \binom{dqp^{\alpha} - 1}{dp^{\alpha} - 1} \right) \equiv 0 \pmod{p^{\alpha + 1}}$$
by the lemma.

17. This completes our induction.

$\blacksquare$