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

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

for each **m** in the sum in (1.11), as for each **i**.
Thus, by Lucas' Theorem, the sum in (1.11) is congruent to
where the sum is over all --tuples of integers
satisfying (6.2) and not all zero. This
is exactly the sum of the coefficients of
in
,
which equals
(1.11) then follows from the induction hypothesis as
and .

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