Difference between revisions of "Lucas' Theorem"
I like pie (talk | contribs) m |
m |
||
Line 1: | Line 1: | ||
− | '''Lucas' Theorem''' states that for any [[prime]] <math>p</math> , if <math>(\overline{n_mn_{m-1}\cdots n_0})_p</math> is the | + | '''Lucas' Theorem''' states that for any [[prime]] <math>p</math> and any [[positive integer]]s <math>n\geq i</math>, if <math>(\overline{n_mn_{m-1}\cdots n_0})_p</math> is the representation of <math>n</math> in [[base]] <math>p</math> and <math>(\overline{i_mi_{m-1}\cdots i_0})_p</math> is the representation of <math>i</math> base <math>p</math> (possibly with some leading <math>0</math>s) then <cmath>\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}.</cmath> |
== Lemma == | == Lemma == |
Revision as of 13:02, 22 April 2008
Lucas' Theorem states that for any prime and any positive integers
, if
is the representation of
in base
and
is the representation of
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
&\equiv&\left((1+x)^{p^k}\right)^p\\ &\equiv&\left(1+x^{p^k}\right)^p\\ &\equiv&\binom{p}{0}+\binom{p}{1}x^{p^k}+\binom{p}{2}x^{2p^k}+\cdots+\binom{p}{p-1}x^{(p-1)p^k}+\binom{p}{p}x^{p^{k+1}}\\
&\equiv&1+x^{p^{k+1}}\pmod{p}\end{eqnarray*}$ (Error compiling LaTeX. Unknown error_msg)Proof
Consider . If
is the base
representation of
, then
for all
and
. We then have
&=&[(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}
\end{eqnarray*}$ (Error compiling LaTeX. Unknown error_msg)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
.