

Line 14: 
Line 14: 
 &\equiv&\binom{p}{0}+\binom{p}{1}x^{p^k}+\binom{p}{2}x^{2p^k}+\cdots+\binom{p}{p1}x^{(p1)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}{p1}x^{(p1)p^k}+\binom{p}{p}x^{p^{k+1}}\\ 
 &\equiv&1+x^{p^{k+1}}\pmod{p}\end{eqnarray*}</cmath>   &\equiv&1+x^{p^{k+1}}\pmod{p}\end{eqnarray*}</cmath> 
− 
 
−  == Proof ==
 
−  Consider <math>(1+x)^n</math>. If <math>(\overline{n_mn_{m1}\cdots n_0})_p</math> is the base <math>p</math> representation of <math>n</math>, then <math>0\leq n_k \leq p1</math> for all <math>0\leq k \leq m</math> and <math>n=n_mp^m+n_{m1}p^{m1}+\cdots+n_1p+n_0</math>. We then have
 
−  <cmath>\begin{eqnarray*}(1+x)^n&=&(1+x)^{n_mp^m+n_{m1}p^{m1}+\cdots+n_1p+n_0}\\
 
−  &=&[(1+x)^{p^m}]^{n_m}[(1+x)^{p^{m1}}]^{n_{m1}}\cdots[(1+x)^p]^{n_1}(1+x)^{n_0}\\
 
−  &\equiv&(1+x^{p^m})^{n_m}(1+x^{p^{m1}})^{n_{m1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}\pmod{p}
 
−  \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_{m1}p^{m1}+\cdots+i_1p+i_0</math>, we want the coefficient of <math>(x^{p^{m}})^{i_{m}}(x^{p^{m1}})^{i_{m1}}\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
 
−  <center><math>\binom{n}{i}\equiv\prod_{k=1}^{n}\binom{n_k}{i_k}\pmod{p}</math></center>
 
−  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^{m1}})^{n_{m1}}\cdots(1+x^p)^{n_1}(1+x)^{n_0}</math>.
 
   
 == See also ==   == See also == 
Latest revision as of 15:13, 11 August 2020