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?
 A: 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.
A: 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)
