info prev up next book cdrom email home

Lucas Correspondence Theorem

Let $p$ be Prime and

$\displaystyle r$ $\textstyle =$ $\displaystyle r_mp^m+\ldots+r_1p+r_0 \qquad (0\leq r_i<p)$ (1)
$\displaystyle k$ $\textstyle =$ $\displaystyle k_mp^m+\ldots+k_1p+k_0 \qquad (0\leq k_i<p),$ (2)

then
\begin{displaymath}
{r\choose k}=\prod_{i=0}^m {r_i\choose k_i} {\rm\ (mod\ } p).
\end{displaymath} (3)

This is proved in Fine (1947).


References

Fine, N. J. ``Binomial Coefficients Modulo a Prime.'' Amer. Math. Monthly 54, 589-592, 1947.




© 1996-9 Eric W. Weisstein
1999-05-25