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:

*
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:

*
where is as in Lemma 1.*

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 (17)
equals

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 *j*th digit when we add *m* and *r* in base *p*; otherwise let
(including ).
We now use (18) to deduce

Now, by (18), we know that the power of

By definition, this equals

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.