proof of Lucas’s theorem

Let nm. Let a0,b0 be the least non-negative residues of n,m(modp), respectively. (Additionally, we set r=n-m, and r0 is the least non-negative residue of r modulo p.) Then the statement follows from


We define the ’carry indicators’ ci for all i0 as


and additionally c-1=0.

The special case s=1 of Anton’s congruenceMathworldPlanetmath is:

(n!)p(-1)npa0!(modp), (1)

where a0 as defined above, and (n!)p is the product of numbers n not divisible by p. So we have


When dividing by the left-hand terms of the congruences for m and r, we see that the power of p is


So we get the congruence


or equivalently

(-1p)c0(nm)(a0b0)(npmp)(modp). (2)

Now we consider c0=1. Since


b0+r0<b0c0=1b0-(p-r0)=a0<b0(a0b0)=0. So both congruences–the one in the statement and (2)– produce the same results.

Title proof of Lucas’s theorem
Canonical name ProofOfLucassTheorem
Date of creation 2013-03-22 13:22:56
Last modified on 2013-03-22 13:22:56
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 7
Author mathcam (2727)
Entry type Proof
Classification msc 11A07
Related topic BinomialCoefficient