Grinstead-Snell-Probability · Problem 37

Combinatorics

Mathematics · binomial-coefficients-modular-arithmetic

Problem

Let n(modm)n \pmod{m} denote the remainder when the integer nn is divided by the integer mm. Write a computer program to compute the numbers (nj)(modm)\binom{n}{j} \pmod{m} where (nj)\binom{n}{j} is a binomial coefficient and mm is an integer. You can do this by using the recursion relations for generating binomial coefficients, doing all the arithmetic using the basic function mod(n,m)\mathrm{mod}(n,m). Try to write your program to make as large a table as possible. Run your program for the cases m=2m = 2 to 7. Do you see any patterns? In particular, for the case m=2m = 2 and nn a power of 2, verify that all the entries in the (n−1)(n-1)st row are 1. (The corresponding binomial numbers are odd.) Use your pictures to explain why this is true.

Related theory

Browse the problem library