Contents Next: Binomial coefficients modulo Up: Arithmetic Properties of Binomial Previous: Introduction.

# Elementary Number Theory and the Proof of Theorem 1.

Wilson's Theorem, which states that , 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.

Contents Next: Binomial coefficients modulo Up: Arithmetic Properties of Binomial Previous: Introduction.