Contents

In (2.1) 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

*
*

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 (3.1), we
need only consider the value of (and
similarly
in (1.8)). Therefore, in order
to compute rapidly
(where **k** is as (1.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 , that (ii) requires and that (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
*

*
*

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

** 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 (3.2), 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
*

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.

** Lemma 3.** * Suppose that for , where
integers.
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 selecting 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.

Contents