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 numbersVarious properties of these functions are discussed in section 5 of : 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 (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 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 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.