# Combinatorics Cameron - Lucas' Theorem Proof

1. Jun 11, 2012

### RiceRiceRice

Combinatorics Cameron -- Lucas' Theorem Proof

Hi everybody --

Im currently going through Peter Cameron's combinatorics book, and I'm having trouble understanding a step in the proof of Lucas' Theorem, given on page 28 for those of you with the book.

The theorem states for p prime,

m = a0 + a1p + . . . + akpk
n = b0 + b1p + . . . + bkpk

where 0 ≤ ai, bi < p for i = 0, . . ., k -1. Then:

(m choose n ) ≡ $\prod$ (ai choose bi ) (mod p), where the product is taken from i = 0 to i = k.

The proof then states:

It suffices to show that, if m = cp + a and n = dp + b, where 0 ≤ a, b < p, then

(m choose n ) $\equiv$ (c choose d) * (a choose b) (mod p) FOR

a = a0
b = b0
c = a1 + . . . + akpk-1
d = b1 + . . . + bkpk-1

I understand the proof of this statement, but I don't know why proving this is sufficient to proving the original theorem.

Any help would be greatly appreciated! Thanks!

2. Jun 11, 2012

### Millennial

Re: Combinatorics Cameron -- Lucas' Theorem Proof

It is the step of induction. Once it is proven, the theorem becomes a corollary.