proof of Lucas’s theorem
Let . Let be the least non-negative residues of , respectively. (Additionally, we set , and is the least non-negative residue of modulo .) Then the statement follows from
We define the ’carry indicators’ for all as
and additionally .
The special case of Anton’s congruence is:
where as defined above, and is the product of numbers not divisible by . So we have
When dividing by the left-hand terms of the congruences for and , we see that the power of is
So we get the congruence
Now we consider . Since
. So both congruences–the one in the statement and (2)– produce the same results.
|Title||proof of Lucas’s theorem|
|Date of creation||2013-03-22 13:22:56|
|Last modified on||2013-03-22 13:22:56|
|Last modified by||mathcam (2727)|