2
$\begingroup$

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

  • 1
    Please provide some more context. Are you talking about [this](http://en.wikipedia.org/wiki/Lucas'_theorem)?2011-12-31
  • 0
    Yes, I am; I am much better at learning from examples though2011-12-31

1 Answers 1

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$.

  • 0
    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?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