how can we check whether a given combination like nCk is divisible by a given prime no. say p…??.
please can some one provide d logic behind it.as it would be too long to evaluate nCk and then check any smarter aproach ?
Yeah .
First see how to find the exponent(power of the prime in prime factorization of the number) of a given prime in a given factorial.
So in n! the exponent of p is floor(n/p) + floor(n/p^2) + … floor(n/p^log (base p ) of n ) .
So to check divisibility of nCk by p , first find the exponent of p in n! . Then find the exponent of p in k! and (n-k)! . Subtract the last two results from the first result . If the final result is zero it is not divisible , if it is greater than 0 , then it is divisible . Please note that final result will never be negative as nCk is always an integer and not a fraction .
3 Likes
well if prime no. p lies between n and (n-k+1) & p > k it will be divisible by p
as nCk = n!/(n-k)!k! which is equal to n*(n-1)…*(n-k+1)/k!
so if it lies in between those n and (n-k+1) & is greater than k ,it wont get cancelled!