Elementary Number Theory.

For a given integer n we define to be the product of those integers that are not divisible by p.

Wilson's Theorem, which states that , may be generalized to prime powers as follows:

For any given prime power we have

where is -1, unless in which case is 1.

This was originally proved by Gauss in Disquisitiones Arithmeticae, the main idea being to multiply each number with its inverse modulo p.

We may deduce from Lemma 1, the following:

For any given prime power , let be the least non-negative residue of . Then

where is as in Lemma 1.

In 1808 Legendre showed that the exact power of p dividing is

(17)

Writing n in base p as above, we define the sum of digits function . Then (17) equals

(18)

These can be proved from a suitable induction hypothesis.

Given integers n and m, we take r=n-m. Define if there is a `carry' in the jth digit when we add m and r in base p; otherwise let (including ). We now use (18) to deduce

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.

the total number of `carries'.

By a similar argument we also have that, for each ,
(19)
The improvement, (2), of Lucas' Theorem is easily deduced from the equation

which was discovered by Anton, Stickelberger and then Hensel. For an arbitrary prime power , we may generalize this result by using the results that we have collected above.