### Mid0's blog

By Mid0, history, 6 years ago,

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 ?

• +6

 » 6 years ago, # | ← Rev. 3 →   0 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; } 
•  » » 6 years ago, # ^ |   0 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 .
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 years ago, # ^ |   0 what is c[][] is your code?
 » 6 years ago, # | ← Rev. 2 →   +12 Once I've coded it in Python, maybe it'll help. (See nCk_mod_prime_power function)Based on this paper by Andrew Granville.
 » 9 months ago, # | ← Rev. 2 →   -20 .