exercise:Bff4875de9

Lucas proved the following general result relating to Exercise. If [math]p[/math] is any prime number, then [math]{n \choose j}~ (\mbox{mod\ }p)[/math] can be found as follows: Expand [math]n[/math] and [math]j[/math] in base [math]p[/math] as [math]n = s_0 + s_1p + s_2p^2 + \cdots + s_kp^k[/math] and [math]j = r_0 + r_1p + r_2p^2 + \cdots + r_kp^k[/math], respectively. (Here [math]k[/math] is chosen large enough to represent all numbers from 0 to [math]n[/math] in base [math]p[/math] using [math]k[/math] digits.) Let [math]s = (s_0,s_1,s_2,\dots,s_k)[/math] and [math]r = (r_0,r_1,r_2,\dots,r_k)[/math]. Then

[[math]] {n \choose j}~(\mbox{mod\ }p) = \prod_{i = 0}^k {{s_i} \choose {r_i}}~(\mbox{mod\ }p)\ . [[/math]]

For example, if [math]p = 7[/math], [math]n = 12[/math], and [math]j = 9[/math], then

[[math]] \begin{eqnarray*} 12 & = & 5 \cdot 7^0 + 1 \cdot 7^1\ , \\ 9 & = & 2 \cdot 7^0 + 1 \cdot 7^1\ , \end{eqnarray*} [[/math]]

so that

[[math]] \begin{eqnarray*} s & = & (5, 1)\ , \\ r & = & (2, 1)\ , \end{eqnarray*} [[/math]]

and this result states that

[[math]] {12 \choose 9}~(\mbox{mod\ }p) = {5 \choose 2} {1 \choose 1}~(\mbox{mod\ }7)\ . [[/math]]

Since [math]{12 \choose 9} = 220 = 3~(\mbox{mod\ }7)[/math], and [math]{5 \choose 2} = 10 = 3~ (\mbox{mod\ }7)[/math], we see that the result is correct for this example. Show that this result implies that, for [math]p = 2[/math], the [math](p^k - 1)[/math]st row of your triangle in Exercise has no zeros.

Notes