# How many numbers $k$ of $200 \choose k$ are divisible by $3$? $k \in \{0,1,2,\cdots 200\}$

"How many of the numbers (200 Choose k), where k is an element of the set {0,1,2,3,4,....,200} are divisible by 3? "

Here is my thinking:

(200 Choose 0,1, and 2) are not multiples of 3 but every next combination has at least 1 multiple of 3 in the numerator therefore making the number divisible by 3. Since there are 201 numbers from 0 to 200, and 3 numbers (0,1, and 2) do not work, there are 198 numbers k.

Is this answer right and is this the right method?

• If $k=9n+r$ , with $r\in\{0,1,2\}$ , then $200\choose k$ does NOT divide through $3$. – Lucian Dec 7 '13 at 21:17
• You must also consider the factors of $3$ in the denominator. $\binom{200}9$ is not divisible by $3$. It’s equal to $$\frac{200\cdot199\cdot\ldots\cdot192}{9!}\;,$$ where the multiples of $3$ in the numerator are $198,195$, and $192$, while those in the denominator are $9,6$, and $3$. There are $4$ factors of $3$ in each, so there are no factors of $3$ in the binomial coefficient. – Brian M. Scott Dec 7 '13 at 21:19
• Where did you get $k = 9n+r$ from? – user113027 Dec 7 '13 at 21:20
• Using J I get that there are 36 $k$'s for which $\binom{200}{k}$ is not divisible by 3. They are: 0 1 2 9 10 11 27 28 29 36 37 38 81 82 83 90 91 92 108 109 110 117 118 119 162 163 164 171 172 173 189 190 191 198 199 200. I used these lines of code (respectively): 201-+/0=3|!&200x i.201 and (#~(-.@(0&=)@(3&|)@(!&200x))) i.201. – rubik Dec 7 '13 at 21:23
• Those calculations confirm @Lucian statement. – rubik Dec 7 '13 at 21:29

According to Lucas' theorem, a binomial coefficient $\binom{m}{n}$ is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m.

$\newcommand{\dcc}{\left\lfloor#1\right\rfloor}$ We know from Legendre's theorem that the power of a prime $p$ in $n!$ is equal to $\sum_{a=1}^\infty \dcc{\frac{n}{p^a}}$. See, for example, Wikipedia, ProofWiki; you can easily find many online resources and books where this result is explained.

We are interested in the power in which the prime 3 appears in the number $\binom{200}k=\frac{200!}{(200-k)!k!}$.

The multiplicity of 3 in 200! is $$\dcc{\frac{200}3}+\dcc{\frac{200}9}+\dcc{\frac{200}{27}}+\dcc{\frac{200}{81}}.$$ We want to compare this number with $$\dcc{\frac{200-k}3}+\dcc{\frac{200-k}9}+\dcc{\frac{200-k}{27}}+\dcc{\frac{200-k}{81}} +\dcc{\frac{k}3}+\dcc{\frac{k}9}+\dcc{\frac{k}{27}}+\dcc{\frac{k}{81}},$$ which is the multiplicity in which $3$ appears in $(200-k)!k!$.

Since $\dcc a +\dcc b\le\dcc{a+b}$, we have \begin{align*} \dcc{\frac{k}3}+\dcc{\frac{200-k}3} &\le \dcc{\frac{200}3}\\ \dcc{\frac{k}9}+\dcc{\frac{200-k}9} &\le \dcc{\frac{200}9}\\ \dcc{\frac{k}{27}}+\dcc{\frac{200-k}{27}} &\le \dcc{\frac{200}{27}}\\ \dcc{\frac{k}{81}}+\dcc{\frac{200-k}{81}} &\le \dcc{\frac{200}{81}} \end{align*} We want to find the values of $k$ for which at least one of these inequalities are strict.

It is useful to notice that the value $\dcc{\frac{k}3}+\dcc{\frac{200-k}3}$ is the same for all $k$'s in the same residue class modulo 3. So it suffices to check $k=0,1,2$ and we see that $$\dcc{\frac{k}3}+\dcc{\frac{200-k}3} = \dcc{\frac{198}3} = \dcc{\frac{200}3}$$ for any $k$. (We tried $k\equiv 0,1,2\pmod3$).

For 9 we get $$\dcc{\frac{k}9}+\dcc{\frac{200-k}9}= \begin{cases} \frac{198}9=22=\dcc{\frac{200}9} & \text{for }k\equiv0,1,2 \pmod9, \\ \frac{191}9=21<\dcc{\frac{200}9} & \text{for }k\equiv3,4,\dots,8 \pmod9 \end{cases}$$

For 27 we get $$\dcc{\frac{k}{27}}+\dcc{\frac{200-k}{27}}= \begin{cases} \frac{189}{27}=7=\dcc{\frac{200}{27}} & \text{for }k\equiv0,1,2,\dots,11 \pmod{27}, \\ \frac{162}{27}=6<\dcc{\frac{200}{27}} & \text{for }k\equiv12,13,\dots,26 \pmod{27} \end{cases}$$

For 81 we get $$\dcc{\frac{k}{81}}+\dcc{\frac{200-k}{81}}= \begin{cases} \frac{162}{81}=2=\dcc{\frac{200}{81}} & \text{for }k\equiv0,1,2,\dots,38 \pmod{81}, \\ \frac{81}{81}=1<\dcc{\frac{200}{81}} & \text{for }k\equiv39,\dots,80 \pmod{81} \end{cases}$$

So the numbers which $k$ for which $\binom{200}k$ is not divisible by $3$ are precisely the numbers which simultaneously fulfill the conditions \begin{align*} k&\equiv0,1,2 \pmod9\\ k&\equiv0,1,2,\dots,11 \pmod{27}\\ k&\equiv0,1,2,\dots,38 \pmod{81} \end{align*} The first two conditions are fulfilled if $k\equiv0,1,2,9,10,11\pmod{27}$. If we add the third condition, we get that this holds for $$k \equiv 0,1,2,9,10,11,27,28,29,36,37,38 \pmod{81}$$ This gives us the 36 possible values $k= 0,1,2,9,10,11, 27,28,29,36,37,38, 81,82,83,90,91,92, 108,109,110,117,118,119, 162,163,164,171,172,173, 189,190,191,198,199,200$.

This coincides with the calculations mentioned in this comment.

See for example N. J. Fine, Binomial coefficients modulo a prime, Am. Math. Monthly 54 (10) (1947) 589-592, http://www.jstor.org/stable/2304500 . See also D. Singmaster, Divisibility of binomial and multinomial coefficients by primes and prime powers, http://www.fq.math.ca/Books/Collection/singmaster.pdf .