# Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?

I was programming the AKS primality test, and I have two questions.

Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)?

Is it correct that if gcd(n, k)>1, then binomial(n, k)>0 (mod n)?

• This looks a math question rather than a CS one. (use then if not comparing) – greybeard Jul 15 '19 at 4:12

All variables are understood to be positive integers. Let $$n\mid m$$ mean $$n$$ is a factor of $$m$$, a.k.a. $$m$$ is divisible by $$n$$ or $$m=0\pmod n$$.

Is it correct that if $$\gcd(n, k)=1$$, then $$n\mid\binom nk$$?

Yes.

Since $$k\binom nk=n\binom{n-1}{k-1}$$, we know $$k\binom nk$$ is divisible by $$n$$. Since $$\gcd(n,k)=1$$, we must have $$\binom nk$$ is divisible by $$n$$.

Is it correct that if $$\gcd(n, k)>1$$, then $$\binom nk>0\pmod n$$?

The relation of "greater than" or "less than" modulo $$n$$ does not make sense since, for example, $$-1=1=2019\pmod 2$$.

What you have in mind should be the following question.

Is it correct that if $$\gcd(n, k)>1$$, then $$n\not\mid\binom nk$$?

Not necessarily.

The smallest counterexample is $$\gcd(10,4)=2\neq1$$ but $$10\mid\binom{10}4=210$$. In fact, if $$n=2\pmod8$$, then $$n\mid\binom n4$$.

Kummer's theorem provides a way to compute the exponent of the highest power of a given prime number dividing a binomial coefficient. Peter Taylor points out that it can be used to determine whether $$n\mid\binom nk$$ in polynomial time if we know the prime factorisation of $$k$$ or $$n$$. However, no algorithm is known to be able to obtain the prime factorisation of an integer in polynomial-time.

Here is a related interesting article, divisibility properties of binomial coefficients by K. R. Mclean.

Exercise 1. Show that if $$m\mid n$$ and $$\gcd(m,k)=1$$, then $$m\mid\binom nk$$.

Exercise 2. Show that $$2i\mid\binom{2i}4$$ iff $$i=1\pmod4$$.

Exercise 3. Find infinitely many pairs of $$n$$ and $$k$$ such that $$1\lt k \mid n$$ and $$n\mid\binom nk$$. (Hint, one such family can be found by setting $$k=6$$.)