In 1852 Kummer showed that the power of prime p which divides the binomial
coefficient 
is given by the number of `carries' when we
add m and n-m in base p.
In 1878 Lucas gave a method to easily determine
the value of 
: Let 
and 
be the least
non--negative residues of m and 
, respectively. Then
where, as usual, 
denotes the largest integer 
,
and we use the convention 
if r<s.
Re--writing 
and
in base p
(so that 
for each i), this may also be expressed
as
We will give three very different proofs of Lucas' Theorem:
the first, via number theory, in section 2;
the second, via cellular automata, in section 5;
and the third, via the combinatorics of power series, in section 6.
Note that if p divides 
then (1.1) follows easily from Kummer's
Theorem. However, if 
is the exact power of p dividing 
,
then we might ask for the value of 
.
This is given by a result discovered by each of Anton (1869),
Stickelberger (1890) and Hensel (1902) (and many others since!), which
shows that
where r = n-m. Numerous authors have asked whether there is an analogous
formula, modulo 
, for arbitrary 
. In section 2 we show
the following:
For a given integer n define 
to be the product of those integers
that are not divisible by p.
Theorem 1. Suppose that prime power 
and positive
integers n=m+r are given. Write 
in base p,
and let 
be the least positive residue of 
for each 
(so that 
).
Also make the corresponding definitions for 
.
Let 
denote the number of `carries', when adding m and r in base p,
on or beyond the jth digit (note that 
here is the same as k above). Then
where 
is 
except if p=2 and 
.
Taking q=1 in (1.3) gives (1.2). Note that (1.3) may be re--written in terms of
factorials, since each 
.
A similar result was recently given by Davis and Webb [4].
Theorem 1 provides a quick way to compute the value of binomial
coefficients modulo arbitrary prime powers. In fact we will show that this takes just
elementary operations, in section 3.
Wilson's Theorem (which actually appears in earlier work of Liebnitz)
states that 
for all primes
p. An easy consequence of this is that
for all integers n.
In 1819 Babbage noticed that, further,
for all primes 
, and
Wolstenholme, in 1862, that
for all primes 
.
In 1952 Ljunggren generalized this to
and Jacobsthal to
for any integers n>m>0 and prime 
, where q
is the power of p dividing 
(this exponent q can only be increased if p divides 
, the
rd Bernoulli number).
These results, as well as many other similar congruences with larger
exponents q, follow easily from Proposition 5 below. For example,
if prime 
then
Ljunggren's result above may be re--written as
for any
integer
and 
. Proposition 5 implies the generalization
unless 
, or 2r+1 = p or 
, when the congruence holds
.
Another generalization of Wolstenholme's congruence is given by
Theorem 2. Suppose that prime p and positive integers u and r are given. Then
except perhaps if 
or 2r+1 = p or 
,
whence the congruence certainly holds 
,
where `
' can only be `-' if p=2 (which is then easily determined
by evaluating both sides of (1.8) modulo 4), and the integer
Remark: In fact 
in Theorem 2 only when p=2 and
is odd.
Note how Theorem 2 allows us to express any 
in terms of 
with 
. Using this result and Theorem 3
below, we will see how to compute factorials 
very rapidly, in section 3.
In 1899 Glaisher observed that the number of odd entries in any given
row of Pascal's Triangle is a power of 2. This follows from Kummer's
Theorem by noting that 
is odd if and only if there
are no carries when adding m and n-m in base 2; in other words that
the digits `1' in the binary expansion of m are a subset of those in the
binary expansion of n. Clearly if there are k digits `1' in the
binary expansion of n, then there are 
possible subsets of these
`1's, and each corresponds to a value of m --- thus there are 
odd entries in the nth row of Pascal's Triangle.
Larry Roberts also has an elegant (unpublished) result, depending on
Kummer's Theorem: Let 
be the binary number whose mth digit
is 
modulo 2; in other words, the integer formed
by reading the nth row of Pascal's Triangle, modulo 2, from left to right.
Then 
, where the sum is over those values of m, for
which the digits `1' in its binary expansion are a subset of those of n.
Thus if 
(where 
)
then
where 
is the ith Fermat number.
As is well known, all odd constructible numbers are of this form; and
thus can be found by reading off the rows of Pascal's Triangle in base 2.
In section 5 we give somewhat different proofs of these last two results, and of Lucas' Theorem, using cellular automata.
In a recent paper [8], using methods from both elementary number theory
and the theory of cellular automata, we extended this result of
Glaisher's to the entries in Pascal's triangle that are 
:
specifically we showed that in any given row of Pascal's triangle,
the number of entries that are congruent to 
is either
0 or a power of 2. Similarly for 
.
We then extended this to 
and 
.
The likelihood of a general result of this type begins to emerge, and
to find out more the reader is encouraged to look at [8].
As is so well known, for any fixed n, the sum, over all m,
of the binomial coefficients 
, is exactly
2 to the power n. What is less well-known is that the
sum of the binomial coefficients, over all m in certain
fixed residue classes, sometimes satisfy certain surprising
congruences:
In 1876 Hermite showed that if n is odd then the sum of the binomial
coefficients 
, over those positive integers m that are
divisible by p-1, is divisible by p.
In 1899 Glaisher generalized this by showing that for
any given prime p and integers 
, we have
for all positive integers 
. We prove this
in section 6.
In 1953 Carlitz generalized Hermite's Theorem to prime
powers: If 
divides n, with 
and 
, then
In 1913 Fleck gave the related result that for
any given prime p and integers 
, we have
where 
.
In 1965 Bhaskaran showed that if p is an odd prime then p+1 divides n if and only if
for 
.
We present proofs of these two results in section 7.
In 1895 Morley [18] showed that for any prime 
,
His ingenious proof, which is based on an explicit form of
De Moivre's Theorem, can be modified
to show that (1.14) holds modulo 
if and only if p divides 
;
however it cannot be modified to investigate other binomial coefficients,
and so we use a different method for this in section 9. We begin by showing, for 
,
for any 
. In fact, this product is 
whenever the p-2nd Bernoulli polynomial vanishes 
at
(which is immediate for m=2).
There are many results in the literature that relate the value
of binomial coefficients of the form
, for a given, fixed d>0
dividing p-1, to representations of the prime p by certain quadratic
forms (see [10]). The first such result, due to Gauss (1828), is for d=4: \
Write any prime 
as 
, and choose
the sign of a so that 
; then
.
Recently, Beukers conjectured that
and this was proved in [3].
In 1846, Jacobi showed that if we write any prime 
as 
, where the sign of A is chosen so that
, then
and this has now been shown to be 
These congruences, modulo 
, have only been discovered quite
recently (in [3]) and there are presumably many others waiting to be found.
Many thanks to the numerous mathematicians who have sent me their comments, results and offprints to include in this survey, particularly Neil Calkin, Fred Howard, Larry Roberts, Herb Wilf and Kenneth Williams.
![[Annotate]](/organics/icons/sannotate.gif){kind=icon}
![[Shownotes]](../gif/annotate/sshow-21.gif)