Lucas' Theorem: If p is a prime number, and N has base p representation (aj,...,a1,a0) and k has base p representation (bj,...,b1,b0), then (N CHOOSE k) is congruent [mod p] to
(aj CHOOSE bj)...(a1 CHOOSE b1)(a0 CHOOSE b0).
Example: Let N = 588, k = 277, p = 5.
N = 588 has base 5 representation (4323).
k = 277 has base 5 representation (2102).
Thus by Lucas' Theorem, (588 CHOOSE 277) is congruent [mod 5] to
(4 CHOOSE 2) (3 CHOOSE 1) (2 CHOOSE 0) (3 CHOOSE 2)
which is 54 = 4 [mod 5].