Mid0's blog

nCr % prime power

By Mid0, history, 11 years ago, In English

i'm trying to calculate nCr mod prime power , i found this comment which is really helpful but the formula as i understand doesn't apply to some numbers and i don't know how it works , could anyone explain it in more details ?

  • Vote: I like it
  • +6
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
11 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Lucas's theorem. WIKI

int calc(int n, int k, int mod) {
  int res = 1;
  while (n || k) {
    res = (res * c[n % mod][k % mod]) % mod;
    n /= mod;
    k /= mod;
  }
  return res;
}
→ Reply
  • »
    »
    11 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    this works well for primes , but it doesn't work for prime power . for example try 28 choose 3 mod 27 it gives zero while the correct answer is nine .

    → Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Lucas' theorem stated that p must be a prime.
    The OP said he needed nCr modulo a prime power (pSomeNumber).

    I'm not sure whether Lucas' theorem still holds.

    → Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it +12 Vote: I do not like it

Once I've coded it in Python, maybe it'll help. (See nCk_mod_prime_power function)

Based on this paper by Andrew Granville.

→ Reply