Grinstead-Snell-Probability · Problem 38

Combinatorics

Mathematics · binomial-coefficients-lucas-theorem

Problem

Lucas proved the following general result relating to Exercise 37. If

p

is any prime number, then

\binom{n}{j} \pmod{p}

can be found as follows: Expand

n

and

j

in base

p

n = s_0 + s_1 p + s_2 p^2 + \cdots + s_k p^k

and

j = r_0 + r_1 p + r_2 p^2 + \cdots + r_k p^k

, respectively. (Here

k

is chosen large enough to represent all numbers from 0 to

n

in base

p

using

k

digits.) Let

s = (s_0, s_1, s_2, \ldots, s_k)

and

r = (r_0, r_1, r_2, \ldots, r_k)

. Then

\binom{n}{j} \pmod{p} = \prod_{i=0}^{k} \binom{s_i}{r_i} \pmod{p}.

For example, if

p = 7

n = 12

, and

j = 9

, then

\begin{aligned} 12 &= 5 \cdot 7^0 + 1 \cdot 7^1, \\ 9 &= 2 \cdot 7^0 + 1 \cdot 7^1, \end{aligned}

so that

s = (5,1)

r = (2,1)

, and this result states that

\binom{12}{9} \pmod{p} = \binom{5}{2}\binom{1}{1} \pmod{7}.

Since

\binom{12}{9} = 220 = 3 \pmod{7}

, and

\binom{5}{2} = 10 = 3 \pmod{7}

, we see that the result is correct for this example. Show that this result implies that, for

p = 2

, the

(p^k - 1)

st row of your triangle in Exercise 37 has no zeros.