Can anyone give me an example of Lucas Theorem and how it works? What about for composite modulus?
Lucas Theorem for combinatorics?
2
$\begingroup$
number-theory
binomial-coefficients
modular-arithmetic
-
1Please provide some more context. Are you talking about [this](http://en.wikipedia.org/wiki/Lucas'_theorem)? – 2011-12-31
-
0Yes, I am; I am much better at learning from examples though – 2011-12-31
1 Answers
5
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$.
-
0So 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? – 2011-12-31
-
3@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. – 2011-12-31
-
0@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$. – 2011-12-31