4
$\begingroup$

Possible Duplicate:
Lucas Theorem but without prime numbers

This question mentions a strategy for computing C(n, k) modulo a composite number, but leaves out the details. The use of the Chinese Remainder Theorem is standard, but I don't follow the suggestion for how to use the extended version of Lucas' Theorem to compute C(n, k) mod p^q.

  • 0
    Thanks, but this link is for Lucas' original Theorem, which only works for primes. I understand Lucas' original Theorem reasonably well.2012-11-22
  • 0
    Maybe [this answer](http://math.stackexchange.com/a/60221/139) is what you're after?2012-11-23
  • 0
    I saw that answer, but it's still a bit opaque to me how that translates into a working algorithm.2012-11-23
  • 0
    Well the answer includes a link to a paper which goes into a little detail on how to turn it into an algorithm.2012-11-23
  • 1
    You saw the above answer, but did *not* link to it in your question and did not elaborate what you did not understand. This makes it impossible to give you a better answer that is not already in the other thread.2012-11-28

0 Answers 0