求(1+x)^2018展开式中被13整除的二项式系数个数（不使用Kummer/Lucas定理）

Let's walk through this problem step by step—no fancy number theory theorems required, just some polynomial arithmetic and base conversion.

First, let's restate the problem clearly: we need to find how many binomial coefficients $\binom{2018}{k}$ (for $k = 0, 1, ..., 2018$) are divisible by 13.

Step 1: Use modular polynomial properties for prime moduli #

Since 13 is a prime, we can use a key observation about polynomials modulo primes:

For any prime $p$, $(1+x)^p \equiv 1 + x^p \pmod{p}$

Why is this true? When you expand $(1+x)^p$, all the middle terms have coefficients $\binom{p}{k}$ where $0 < k < p$. Each of these coefficients is divisible by $p$ (since $p$ is prime and appears in the numerator but not the denominator), so they vanish modulo $p$. Only the first and last terms remain.

We can extend this to higher powers. If we write $n$ as a sum of powers of $p$ (i.e., its base-$p$ expansion), then:
$$(1+x)^n = (1+x)^{a_0 + a_1p + a_2p^2 + ...} = (1+x)^{a_0} \cdot \left[(1+x)^p\right]{a_1} \cdot \left[(1+x)^{p2}\right]^{a_2} \cdot ...$$

Modulo $p$, this simplifies to:
$$(1+x)^{a_0} \cdot (1+x^p){a_1} \cdot (1+x^{p2})^{a_2} \cdot ...$$

Step 2: Connect this to binomial coefficients modulo 13 #

When we expand this product, each term corresponds to picking a term from each factor:

• From $(1+x)^{a_0}$, we pick $\binom{a_0}{k_0}x^{k_0}$ (where $0 \leq k_0 \leq a_0$)
• From $(1+x^p){a_1}$, we pick $\binom{a_1}{k_1}x^{k_1p}$ (where $0 \leq k_1 \leq a_1$)
• From $(1+x^{p2})^{a_2}$, we pick $\binom{a_2}{k_2}x^{k_2p2}$ (where $0 \leq k_2 \leq a_2$)
• And so on...

Multiplying these together gives a term $\left(\binom{a_0}{k_0}\binom{a_1}{k_1}\binom{a_2}{k_2}...\right)x^{k_0 + k_1p + k_2p^2 + ...}$. The coefficient here is exactly $\binom{2018}{k}$ modulo 13, where $k = k_0 + k_1p + k_2p^2 + ...$ (the base-13 expansion of $k$).

Now, $\binom{2018}{k}$ is divisible by 13 if and only if this product of coefficients is congruent to 0 modulo 13. Let's break this down:

• Each $\binom{a_i}{k_i}$ is an integer between 1 and $\binom{a_i}{a_i}=1$ (or 0 if $k_i > a_i$). Since $a_i$ is a digit in the base-13 expansion of 2018, $0 \leq a_i < 13$, so $\binom{a_i}{k_i}$ can't be divisible by 13 (it's a product of numbers smaller than 13, no factor of 13 exists).
• The only way the product is 0 modulo 13 is if at least one $\binom{a_i}{k_i} = 0$, which happens when $k_i > a_i$ (you can't choose more elements than you have).

Step 3: Calculate the base-13 expansion of 2018 #

Let's convert 2018 to base 13:

• $2018 \div 13 = 155$ with remainder 3 → the $13^0$ (units) digit is 3
• $155 \div 13 = 11$ with remainder 12 → the $13^1$ digit is 12
• $11 \div 13 = 0$ with remainder 11 → the $13^2$ digit is 11

So 2018 in base 13 is $(11, 12, 3)_{13}$, meaning $2018 = 11 \cdot 13^2 + 12 \cdot 13 + 3$.

Step 4: Count coefficients NOT divisible by 13 #

A coefficient $\binom{2018}{k}$ is not divisible by 13 if every digit in $k$'s base-13 expansion is ≤ the corresponding digit in 2018's base-13 expansion:

• For the $13^2$ digit: $k_2$ can be 0 to 11 → 12 choices
• For the $13^1$ digit: $k_1$ can be 0 to 12 → 13 choices
• For the $13^0$ digit: $k_0$ can be 0 to 3 → 4 choices

Total non-divisible coefficients: $12 \times 13 \times 4 = 624$.

Step 5: Find the number of divisible coefficients #

Total binomial coefficients: $2018 + 1 = 2019$ (since $k$ ranges from 0 to 2018).

Subtract the non-divisible count from the total:
$$2019 - 624 = 1395$$

So there are 1395 binomial coefficients in the expansion of $(1+x)^{2018}$ that are divisible by 13.

内容的提问来源于stack exchange，提问作者Rohan Shinde