Difference between revisions of "Lucas' Theorem"
Line 1: | Line 1: | ||
Let <math>p</math> be a prime. If <math>(\overline{n_mn_{m-1}\cdots n_0})_p</math> is the base <math>p</math> representation of <math>n</math> and <math>(\overline{i_mi_{m-1}\cdots i_0})_p</math> is the base <math>p</math> representation of <math>i</math>, where <math>n\geq i</math>, '''Lucas' Theorem''' states that <cmath>\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}</cmath> | Let <math>p</math> be a prime. If <math>(\overline{n_mn_{m-1}\cdots n_0})_p</math> is the base <math>p</math> representation of <math>n</math> and <math>(\overline{i_mi_{m-1}\cdots i_0})_p</math> is the base <math>p</math> representation of <math>i</math>, where <math>n\geq i</math>, '''Lucas' Theorem''' states that <cmath>\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}</cmath> | ||
− | + | == Lemma == | |
− | |||
For <math>p</math> prime and <math>x,r\in\mathbb{Z}</math>, | For <math>p</math> prime and <math>x,r\in\mathbb{Z}</math>, | ||
<cmath>(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}</cmath> | <cmath>(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}</cmath> | ||
Line 12: | Line 11: | ||
&\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&\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*}</math></center> | &\equiv&1+x^{p^{k+1}}\pmod{p}\end{eqnarray*}</math></center> | ||
+ | |||
+ | == Proof == | ||
+ | Consider the <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 have <center><math>\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}\\ | ||
+ | &\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*}</math></center>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>. The coefficient of each <math>(x^{p^{k}})^{i_{k}}</math> comes from the binomial expansion of <math>(1+x^{p^k})^{n_k}</math>, which is <math>\binom{n_k}{i_k}</math>. Therefore we take the product of all such <math>\binom{n_k}{i_k}</math>, and thus we have <cmath>\binom{n}{i}\equiv\prod_{k=1}^{n}\binom{n_k}{i_k}\pmod{p}</cmath>Note that <math>n_k<i_k\Longrightarrow\binom{n_k}{i_k}=0\Longrightarrow\binom{n}{i}\equiv 0 \pmod{p}</math>. This is equivalent to saying that there is no <math>x^i</math> term in the expansion of <math>(1+x)^n=(1+x^{p^m})^{n_m}(1+x^{p^{m-1}})^{n_{m-1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}</math>. | ||
+ | |||
+ | == Example == | ||
== Links == | == Links == | ||
Line 19: | Line 26: | ||
* [[Combinatorics]] | * [[Combinatorics]] | ||
* [[Generating function]] | * [[Generating function]] | ||
+ | * [[Binomial Theorem]] | ||
[[Category:Theorems]] | [[Category:Theorems]] |
Revision as of 16:38, 8 November 2007
Let be a prime. If
is the base
representation of
and
is the base
representation of
, where
, Lucas' Theorem states that
Lemma
For prime and
,
Proof
For all ,
. Then we have that
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 the . If
is the base
representation of
, then
for all
and
. We 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
Note that
. This is equivalent to saying that there is no
term in the expansion of
.