Difference between revisions of "Lucas' Theorem"
Mathgeek2006 (talk | contribs) m (→Proof) |
Mathgeek2006 (talk | contribs) m (→Proof) |
||
Line 17: | Line 17: | ||
== Proof == | == Proof == | ||
Consider <math>(1+x)^n</math>. If <math>(\overline{n_mn_{m-1}\cdots n_0})_p</math> is the base <math>p</math> representation of <math>n</math>, then <math>0\leq n_k \leq p-1</math> for all <math>0\leq k \leq m</math> and <math>n=n_mp^m+n_{m-1}p^{m-1}+\cdots+n_1p+n_0</math>. We then have | Consider <math>(1+x)^n</math>. If <math>(\overline{n_mn_{m-1}\cdots n_0})_p</math> is the base <math>p</math> representation of <math>n</math>, then <math>0\leq n_k \leq p-1</math> for all <math>0\leq k \leq m</math> and <math>n=n_mp^m+n_{m-1}p^{m-1}+\cdots+n_1p+n_0</math>. We then have | ||
− | < | + | <cmath>\begin{eqnarray*}(1+x)^n&=&(1+x)^{n_mp^m+n_{m-1}p^{m-1}+\cdots+n_1p+n_0}\\ |
&=&[(1+x)^{p^m}]^{n_m}[(1+x)^{p^{m-1}}]^{n_{m-1}}\cdots[(1+x)^p]^{n_1}(1+x)^{n_0}\\ | &=&[(1+x)^{p^m}]^{n_m}[(1+x)^{p^{m-1}}]^{n_{m-1}}\cdots[(1+x)^p]^{n_1}(1+x)^{n_0}\\ | ||
&\equiv&(1+x^{p^m})^{n_m}(1+x^{p^{m-1}})^{n_{m-1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}\pmod{p} | &\equiv&(1+x^{p^m})^{n_m}(1+x^{p^{m-1}})^{n_{m-1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}\pmod{p} | ||
− | \end{eqnarray*}</ | + | \end{eqnarray*}</cmath> |
We want the coefficient of <math>x^i</math> in <math>(1+x)^n</math>. Since <math>i=i_mp^m+i_{m-1}p^{m-1}+\cdots+i_1p+i_0</math>, we want the coefficient of <math>(x^{p^{m}})^{i_{m}}(x^{p^{m-1}})^{i_{m-1}}\cdots (x^p)^{i_1}x^{i_0}</math>. | We want the coefficient of <math>x^i</math> in <math>(1+x)^n</math>. Since <math>i=i_mp^m+i_{m-1}p^{m-1}+\cdots+i_1p+i_0</math>, we want the coefficient of <math>(x^{p^{m}})^{i_{m}}(x^{p^{m-1}})^{i_{m-1}}\cdots (x^p)^{i_1}x^{i_0}</math>. | ||
Revision as of 19:11, 10 March 2015
Lucas' Theorem states that for any prime and any positive integers
, if
is the representation of
in base
and
is the representation of
in base
(possibly with some leading
s) then
.
Contents
Lemma
For prime and
,
![$(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}$](http://latex.artofproblemsolving.com/7/9/3/7931ec8ec0b821c30647d45a9013d573cf554bac.png)
Proof
For all ,
. Then we have
Assume we have
. Then
Proof
Consider . If
is the base
representation of
, then
for all
and
. We then have
We want the coefficient of
in
. Since
, we want the coefficient of
.
The coefficient of each comes from the binomial expansion of
, which is
. Therefore we take the product of all such
, and thus we have
![$\binom{n}{i}\equiv\prod_{k=1}^{n}\binom{n_k}{i_k}\pmod{p}$](http://latex.artofproblemsolving.com/a/d/e/ade39455e7ebe16ed682cb84a73ebafaff3173bf.png)
Note that .
This is equivalent to saying that there is no term in the expansion of
.