Binomial coefficients mod primes

Imagine seeing the following calculation:

{95 \choose 57} = {19\cdot 5 \choose 19\cdot 3} = {5 \choose 3} = \frac{5\cdot 4}{2\cdot 1} = 10

The correct result is

{95 \choose 57} = 487343696971437395556698010

and so the first calculation is off by 25 orders of magnitude.

But there’s a variation on the calculation above that is correct! A theorem by Édouard Lucas from 1872 that says for p prime and for any nonnegative integers m and n,

{pm \choose pn} = {m \choose n} \bmod p

So while the initial calculation was grossly wrong as stated, it is perfectly correct mod 19. If you divide 487343696971437395556698010 by 19 you’ll get a remainder of 10.

A stronger versions of Lucas’ theorem [1] says that if p is at least 5, then you can replace mod p with mod p³. This is a stronger conclusion because it says not only is the difference between the left and right side of the congruence divisible by p, it’s also divisible by p² and p³.

In our example, not only is the remainder 10 when 487343696971437395556698010 is divided by 19, the remainder is also 10 when dividing by 19² = 361 and 19³ = 6859.

More on binomial coefficients

[1] V. Brun, J. O. Stubban, J. E. Fjeldstad, L. Tambs, K. E. Aubert, W. Ljunggren, E. Jacobsthal. On the divisibility of the difference between two binomial coefficients, Den 11te Skandinaviske Matematikerkongress, Trondheim, 1949, 42–54.

2 thoughts on “Binomial coefficients mod primes

  1. @Severin, that depends on whether you read the equation like a programmer or like a mathematician. I’m using it in the latter sense.

    A programmer would read “a == b mod p” to mean that the integer a equals the result of applying the mod p operator to b.

    A mathematician reads “a = b mod p” to mean that (a – b) is divisible by p.

    So a mathematician could say “23 = 53 mod 10”, but the boolean expression “23 == 53 % 10” in C would be false.

Leave a Reply

Your email address will not be published. Required fields are marked *