Binomial coefficients modulo prime powers.

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

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 (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

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.