2
$\begingroup$

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

  • 0
    Yes, I am; I am much better at learning from examples though2011-12-31

1 Answers 1

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