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
-
0Yes, I am; I am much better at learning from examples though – 2011-12-31
1 Answers
6
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$.
-
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