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 (21)
where the integer
and non-negative
integers u and v are given with 
. Then
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 (22)
, integer
u and rational
y, whose denominator is not divisible by p, we have
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
where
for each 
and distinct 
,
we have
.
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.