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.