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 Edouard 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^3. 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^2 and p^3.
In our example, not only is the remainder 10 when 487343696971437395556698010 is divided by 19, the remainder is also 10 when dividing by 19^2 = 361 and 19^3 = 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.