# Divisibility criterion of binomial coefficients

If $r\in\Bbb Z_{\geq0}$ and $m$ is odd then let $2^\ell\mid\binom{m}{2^r}$ and $2^{\ell+1}\nmid\binom{m}{2^r}$.

Is there a way to find if $\ell$ is even or odd without computing $\binom{m}{2^r}$ (assume $\ell$ odd if $m<2^r$)?

Lucas theorem states $\ell$ is number of carries when $m-2^r$ is added to $2^r$.

However we look for less information and may be we can get away from explicit adding and using other type of operations.

• If $r\le k$, at least, then one just has $\ell=k-r$. – Harry Altman Dec 29 '17 at 5:03
• @HarryAltman why? – Turbo Dec 29 '17 at 5:04
• You asked about avoiding the calculation of $\binom{m}{2^r}.$ As you already know , $\ell$ can easily be found exactly without computing that value. It appears from your comments that you wonder about finding the parity of $\ell$ without actually finding $\ell$ itself. The method of finding $\ell$ works as well for any $\binom{m}{t}.$ Instead of counting the carries $1,2,3,\cdots$ you could count even,odd,even,odd,$\cdots$" – Aaron Meyerowitz Dec 29 '17 at 7:17

The exponent $\ell$ is the same as the maximal $\ell$ for which $2^\ell$ divides $\lfloor m/2^r\rfloor$. This follows from the criterion with carries or may be proved directly.
• Yeah but that gets $\ell$ and that is too much. – Turbo Dec 29 '17 at 6:21
• Ok, so essentially your question is whether we may find the parity of $\ell$ faster than $\ell$ itself, right? I guess it depends on how you represent your number. If $m=2^{n_0}+2^{n_1}+\dots$ for $n_0<n_1<\dots$ is a binary decomposition of $m$, and it is given (and all $n_i$'s are given also in binary), then you find minimal $i$ for which $n_i>r$ and look at the parity of $n_i$. – Fedor Petrov Dec 29 '17 at 7:04