1
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ This looks a math question rather than a CS one. (use then if not comparing) $\endgroup$ – greybeard Jul 15 at 4:12
1
$\begingroup$

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$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.