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  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
 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.
3 thoughts on “Binomial coefficients mod primes”
Shouldn’t `mod p` go on the left side?
@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.
Mathematicians usually put the “mod p” part in parentheses.