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.

  • $\begingroup$ How about applying math.stackexchange.com/questions/141196/… on $$\binom{2018}r$$ $\endgroup$ – lab bhattacharjee Feb 5 '18 at 6:08
  • $\begingroup$ @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. $\endgroup$ – 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
   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$.

  • $\begingroup$ Is there any method to do such questions by hand I mean without computer software? $\endgroup$ – Rohan Shinde Feb 5 '18 at 6:22
  • $\begingroup$ Yes: use Kummer's theorem. But you said you didn't want that. $\endgroup$ – Robert Israel Feb 5 '18 at 6:29
  • $\begingroup$ 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. $\endgroup$ – 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$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.