In (20) above we saw how any may be expressed, modulo ,
in terms of values of with : this was
the key fact behind Proposition 1 and Theorem 1. In this section we
prove the following result which allows us to express ,
modulo , in terms of with *k < qp*:
Given integers define
.

* Theorem 3.* * Suppose that prime power and non-negative
integers u and v are given with . Then
*

**(21)**

*
where the integer
*

*
*

Now, given , where , first write and then compute using Theorem 2, and using Theorem 3: We are thus able to express in terms of and , with .

Notice that any , so that
: Thus, in (21), we
need only consider the value of (and
similarly
in (8)). Therefore, in order
to compute rapidly
(where *k* is as (2)), we suggest the following algorithm:\

i) Use Theorem 1 to re-express as a product of integers of the form with .

ii) Write each such *a* as *up+v* with , and then
use Theorems 2 and 3 to write each such in terms of
with *b < qp*, to powers no larger than .

iii) Compute each with *b < qp*, and then
take each of these to the required power.

An elementary analysis reveals that (i) requires , (ii) requires and (iii) requires elementary operations, so that this algorithm typically produces enormous savings over just using Theorem 1.

In order to prove Theorem 3, we need the following

* Proposition 2.* * For any given prime power , integer
u and rational
y, whose denominator is not divisible by p, we have
*

**(22)**

* *

*
*

Theorem 3 then follows by taking the product of the equation in Proposition 2,
with , for each that is not divisble by *p*.

Henceforth let if and if *p=2*.
Eisenstein (1850) and Kummer (1851) introduced the *p*-* adic logarithm*
and *p*-* adic exponential* functions:
Given a rational number *x*, define *p*-adic numbers

Various properties of these functions are discussed in section 5 of Washington's book:
For instance if *p* divides both *x* and *y* then
.
Moreover if divides *x* then and
;
also the highest power of *p* dividing *x* is the same as that dividing
. These properties will be vital in our proofs of Theorems 2
and 3.

* The Proof of Propositon 2:* If then the result is
trivial, so assume . Now take the *p*-adic logarithm of the
quotient of the two sides of (22), so that the result is equivalent to
proving that
, where
. We shall actually
prove that each individual term, , of the sum is
. For those terms with we use

* Lemma 2.* * Given and distinct ,
we have
*

*
where
*

*
for each .*

This may be verified in a number of ways, for instance by inverting the relevant Vandermonde determinant.

Now, taking and each other in Lemma 2, we find that for each , and so for . Note that each , and so is an integer.

For those terms with we use

* Lemma 3.* * Suppose that integers
are given with
for .
Then is divisible by m, whenever
. *

* Proof:* If divides *m* then divides and
, so that
.
The result follows from the Chinese Remainder Theorem.

Thus taking and, otherwise, the 's and 's as before, we find that is an integer for , by Lemma 3, and so .

Finally note that the power of *p* dividing *m* is (trivially) ,
so that the power of *p* dividing is . Thus
whenever as
each is an integer.