,
may be generalized to prime powers as follows:
Lemma 1. For any given prime power 
we have
where 
is as in Theorem 1.
This was proved by Gauss in Disquisitiones Arithmeticae,
as follows:\
If we pair up each m in the product with its inverse 
then we see that 
is congruent, modulo 
, to the product of
those 
that are not distinct from their inverses 
,
that is those m for which 
. It is
easy to show that the only such m are 1 and 
unless 
(when one only has m=1) or 
when one has the additional
solutions 
and 
. The result follows.
We may deduce from Lemma 1 the following
Corollary 1. For any given prime power 
let 
be the least non-negative residue of 
.
Then
where 
is as in Theorem 1.
Proof: Write each r in the product below as 
, to get
by Lemma 1, where 
signifies
a product over integers not divisible by p.
In 1808 Legendre showed that the exact power of p dividing 
is
Writing n in base p as above, we define the sum of digits function
. Then (2.2)
equals
These are both easily proved by an induction hypothesis: If n<p
(that is 
) then clearly p does not divide 
and both (2.2) and
(2.3) equal zero. So, given 
, note that the set of integers 
that are divisible by p are precisely the set of integers pk for
. Thus the power of p dividing 
is exactly 
plus the power of p dividing 
. (2.2) then follows immediately
from the induction hypothesis, and (2.3) after noting that
Let r = n-m and write each of
n, m and r in base p. Let 
if there is a `carry'
in the jth digit when adding m and r in base p, let
otherwise (including 
).
We use (2.3) to deduce
Kummer's Theorem. The power to which prime
p divides the binomial coefficient 
is given
by the number of `carries' when we add m and n-m in base p.
Proof:
One can easily check that, for each integer 
,
Now, by (2.3), the power of p dividing 
is
By definition, this equals
the total number of `carries'.
By a similar argument we also have, for each 
, that
This can be seen by letting 
be the least residues, in absolute
value, of 
, respectively, so that 
times the
left side of (2.4), plus 
equals n-m-r = 0. However,
and (2.4) follows.
The improvement, (1.2), of Lucas' Theorem is easily deduced from the equation
which was discovered by Anton, Stickelberger and then Hensel.
For an arbitrary prime power 
, this may be generalized
as follows:
With definitions as in Theorem 1, we have, for any given 
,
by Corollary 1. Multiplying together this congruence for each 
we get
Proposition 1. For any integer n and prime power 
,
we have
where 
and each 
are as in Theorem 1.
Theorem 1 then follows from dividing the equation in Proposition 1 by
the corresponding ones for m and r, and then using (2.4) to sort
out the exponents of 
and p.
![[Annotate]](/organics/icons/sannotate.gif){kind=icon}
![[Shownotes]](../gif/annotate/sshow-31.gif)