Binomial coefficients mod primes

Imagine seeing the following calculation: The correct result is 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, 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 Binomial coefficient trick Maximum gap between binomial coefficients Lebesgue’s proof of Weierstrass’ theorem [1] V.

Brun, J.


Stubban, J.


Fjeldstad, L.

Tambs, K.


Aubert, W.

Ljunggren, E.


On the divisibility of the difference between two binomial coefficients, Den 11te Skandinaviske Matematikerkongress, Trondheim, 1949, 42–54.


Leave a Reply