Problem:
Let , be integers chosen independently and uniformly at random from the set . Compute the expected value of the remainder when the binomial coefficient is divided by . (Here and whenever .)
Problem:
Let , be integers chosen independently and uniformly at random from the set . Compute the expected value of the remainder when the binomial coefficient is divided by . (Here and whenever .)
Solution:
Answer:
By Lucas' Theorem we're looking at
where the and are the digits of and in base . If any , then the product is zero modulo .
Otherwise, the potential residues are , , , , , .
So each term in the product has a chance of being zero; given that everything is nonzero, each term has a chance of being and a chance of being . The probability that an even number of terms are given that none are zero is then given by the roots of unity filter
Thus the expected value is