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

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.