# How to check if $k$ divides $\binom {n - 1} {k - 1}$ cheaply?

I'm writing a computer algorithm to do binomial expansion in C#. You can view the code here; I am using the following identity to do the computation:

$$\dbinom n k = \frac n k \dbinom {n - 1} {k - 1}$$

Currently, the algorithm computes $\dbinom {n - 1} {k - 1}$, multiplies it by $n$, then divides by $k$. Since signed integers are capped at $2^{32} - 1$ on a computer, which can be a very small limit for large $n$, I want to change the algorithm to divide by $k$ before mixing in $n$. However, computer integer division floors the result if the dividend isn't a multiple of the divisor; for example, $11 / 5 = 2$. So I want to come up with a criteria for whether $k$ divides $\dbinom {n - 1} {k - 1}$ that can be cheaply checked.

Here's my work so far: assuming $n > k$, then $n - 1 \geq k$. Then $(n - 1)!$ will have at least 1 factor of $k$, and $k \mid \dbinom {n - 1} {k - 1}$ if the $(k - 1)!(n - k)!$ factor does not cancel those factors out. If $k$ is prime, then $(k - 1)!$ will have no factors of $k$. $(n - k)!$ will often have less factors of $k$ than $(n - 1)!$, but that is not the case if $n \equiv -1 \mod k$. For example, $5 \not\mid \dbinom 9 4$, because both the numerator and denominator have exactly one factor of $5$.

So I figured out that $n \not\equiv -1 \mod k$ must be true for primes, but I've no idea how to deal with composites. I played around a bit with them, though, and $6$ is another value of $k$ for which $6 \not\mid \dbinom 11 5$, so clearly $k$ doesn't have to be prime. Any tips?

If division by $k$ would give you a non-integer, multiplication by $n$ would give you back an integer. So if you reduce $n/k$ to lowest terms, $n/k = a/b$ with $\gcd(a,b) = 1$, then you can safely divide by $b$ and then multiply by $a$.

EDIT: Another method: Let $q$ be the result of integer division of $N = {n-1 \choose k-1}$ by $k$, and $r = N - q k$ (so $0 \le r < k$ and $N \equiv r \mod k$). Then $\frac{n N}{k} = n q + (n r)/k$, where the multiplication $n r$ is much less likely to produce an overflow.

• Thank you, that's a pretty ingenious solution. It is not computationally cheap to reduce a fraction to simplest terms, though (you have to find the GCD, which takes non-constant time). I might end up using this method if no other solutions are available, however. – James Ko Apr 29 '17 at 1:16
• Your second solution pretty much hit the mark, since $q$ can be easily gotten by dividing by $k$ and calculating $r$ with a couple of subtractions/multiplications is pretty cheap. For anyone interested, here is the new revision of my binomial algorithm: gist.github.com/jamesqo/d4ccd1c159479bc6b48b58933180a200 – James Ko Apr 29 '17 at 4:53

You might be better off memoizing the traditional formula? If you have a 32-bit roof there isn't much that can take that long.

    #include <stdio.h>
#define N 50
int cache[N][N];

int f(int n, int k) {
if (k == 0 || k == n) {
return 1;
}
if (cache[n][k] != 0) {
return cache[n][k];
}
cache[n][k] = f(n-1, k-1) + f(n-1, k);
return cache[n][k];
}

int main() {
printf("%d\n", f(2*15, 15));
}


Edit: as per comment, got rid of bad idea for dealing with leafs of recursion (sorry wrote the original when sleep deprived)

• Interesting method. Why did you choose not to cache and do recursion for values below 2^16, though? – James Ko Apr 29 '17 at 4:49