# Lucas Theorem for combinatorics?

Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?

-
Please provide some more context. Are you talking about this? – Srivatsan Dec 31 '11 at 18:41
Yes, I am; I am much better at learning from examples though – WhatsInAName Dec 31 '11 at 18:45

## 1 Answer

Let $p=3$, let $m=44=(1122)_3$, and let $n=14=(112)_3$. Then Lucas's Theorem says that $$\binom{44}{14}\equiv\binom{1}{0}\binom{1}{1}\binom{2}{1}\binom{2}{2}\bmod 3,$$ i.e. $$114955808528\equiv 1\cdot1\cdot2\cdot1\equiv 2\bmod 3.$$ This is correct; when we divide $114955808528$ by $3$, we get $38318602842$ with a remainder of $2$.

-
So it's taking the digits of m and n in base p and finding a bunch of mini combinatorics? Is there also a way to do this for nonprime mod? What if p is larger than 10, where digits are no longer single digits? – WhatsInAName Dec 31 '11 at 19:12
@user1123950: For nonprime modulus, you can use the Chinese Remainder Theorem. For example, if you want a computation mod $105=3\cdot5\cdot7$, you just need to do the computation mod 3, then mod 5, then mod 7 (using Lucas's Theorem) and combine the results. But Lucas's Theorem does not tell you the result modulo higher powers of p. If you want to do a computation modulo $75=3\cdot5^2$, you just need to do the computation mod 3 and then mod $5^2$; but there are no shortcuts as nice as Lucas's Theorem for the mod $5^2$ computation. – Jonas Kibelbek Dec 31 '11 at 22:55
@user1123950: Lucas's Theorem works just fine for primes larger than 10; just be sure you understand base $b$ expansions of integers. If you use $p=17$, you will use base 17 expansions, which use as digits $0, 1, 2, \ldots, 14, 15, 16$. – Jonas Kibelbek Dec 31 '11 at 22:58