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 jth digit when we add m and r in base p; otherwise let (including ). We now use (18) to deduce
the total number of `carries'.
By a similar argument we also have that,
for each ,
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.