Computing binomial coefficients modulo prime powers.

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


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


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


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.