Contents Next: Sums of Binomial Up: Arithmetic Properties of Binomial Previous: Pascal's triangle via

Studying binomial coefficients through their generating function.

We begin this section with another proof of Lucas' Theorem (due to Fine (1947)), based on the obvious generating function for

: Start by noting that

as each

is divisible by p, by Kummer's Theorem, unless i=0 or

(this is sometimes referred to as ` The Children's Binomial Theorem'). Therefore, writing n in base p, we have

and the result follows.

We can use the same approach to try to prove the analogue of Lucas' Theorem modulo

, and arbitrary prime powers, but the details become much more complicated than in the proof given in section 2. We may also generalize this method to evaluate, modulo p, the coefficients of powers of any given polynomial:

Given a polynomial of degree d, with integer coefficients, we will define , and let if m<0 or m>nd (note that when ). Clearly using Fermat's Theorem, and so

Given m, let

be the least non-negative residue of

. Therefore if m = pt+r then r must be of the form

with

. Thus we obtain the following generalization of (1.1):

We use a similar approach in the

Proof of (1.11): By induction on n: For we must have n=k and the only possible value of m in the sum is j, so that the result is trivial. Now assume that , and write m and n in base p. Then