# Divisiblity of binomial coefficients

Find the number of binomial coefficients in the expansion of $(1+x)^{2018}$ that are divisible by $13$

On searching the internet for a long time I found that these type of questions are relevantly solved using either Kummer 's theorem or the Luca's theorem. But I haven't studied them yet. So can someone please explain some method to solve these problem without using those theorems.

• How about applying math.stackexchange.com/questions/141196/… on $$\binom{2018}r$$ – lab bhattacharjee Feb 5 '18 at 6:08
• @lab bhattacharjee I don't get how would you apply that method to this question. The $r$ is variable here.Morever that question deals with factorials while this question is related to binomial coefficients. – Rohan Shinde Feb 5 '18 at 6:11

You could use semi-brute force: simply compute rows $0$ to $2018$ of Pascal's triangle mod $13$, and count the $0$'s in row $2018$. In Maple:

   A[0]:= [1];
for r from 1 to 2018 do
A[r]:= [0,op(A[r-1])]+[op(A[r-1]),0] mod 13
od:
numboccur(0, A[2018]);


EDIT: Here is the solution using Kummer's theorem. The theorem says that the exponent of prime $p$ in the factorization of ${n \choose k}$ is the number of carries in addition of $k$ and $n-k$ in base $p$. Thus in order for $n \choose k$ not to be divisible by $p$, what you need is that the base $p$ addition of $k$ and $n-k$ has no carries.

In our case, $2018$ in base $13$ is $bc3$ (where $b$ represents $11$ and $c$ represents $12$, i.e. $2018 = 3 + 12 \times 13 + 11 \times 13^2$.

If the base $13$ digits of $k$ (with possible leading $0$'s) are $k_2, k_1, k_0$, and there are no carries, then the digits of $2018-k$ must be $11-k_2$, $12-k_1$ and $3-k_0$. There are $12$ possibilities for $k_2$ ($0$ to $11$), $13$ possibilities for $k_1$, and $4$ possibilities for $k_0$, for a total of $12 \times 13 \times 4 = 624$ cases where ${2018\choose k}$ is not divisible by $13$. Of the $2019$ values of $k$ from $0$ to $2018$, the remaining $2019 - 624 = 1395$ will thus have ${2018 \choose k}$ divisible by $13$.

• Is there any method to do such questions by hand I mean without computer software? – Rohan Shinde Feb 5 '18 at 6:22
• Yes: use Kummer's theorem. But you said you didn't want that. – Robert Israel Feb 5 '18 at 6:29
• Okay then can you post the solution using Kummer 's theorem. I will try to learn myself what Kummer's theorem is and how to apply it. – Rohan Shinde Feb 5 '18 at 6:35

$$E_{13}(2018!)=\left \lfloor \frac {2018}{13}\right \rfloor+\left \lfloor \frac {2018}{13^2}\right \rfloor+\left \lfloor \frac {2018}{13^3}\right \rfloor \ldots$$ $$=155+11+0$$ $$=166$$

$$\Rightarrow E_{13}(r!) +E_{13}((2018-r)!)\le 165$$ $$\Rightarrow r=13\lambda +k, k=4,5,6,7,8,9,10,11,12$$

For $r=13\lambda+ 4$ we have following $155$ numbers $$r=4,17,30,....., 2006$$

And continue similarly for other values of $k$

$$\Rightarrow Total = 155*9=1398$$

• @JyrkiLahtonen ping you where? And thanks for the support :-) – Rohan Shinde Feb 21 '18 at 10:58
• Wherever you can find me :-) Deleting the earlier comment. It is not for all eyes. – Jyrki Lahtonen Feb 21 '18 at 11:31