Difference between revisions of "Lucas' Theorem"
(New page: 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...) |
m (→Proof) |
||
| Line 2: | Line 2: | ||
== Proof == | == Proof == | ||
| + | === Lemma === | ||
| + | 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> | ||
| + | === Proof === | ||
| + | For all <math>1\leq k \leq p-1</math>, <math>\binom{p}{k}\equiv 0 \pmod{p}</math>. Then we have that <center><math>\begin{eqnarray*}(1+x)^p&\equiv &\binom{p}{0}+\binom{p}{1}x+\binom{p}{2}x^2+\cdots+\binom{p}{p-1}x^{p-1}+\binom{p}{p}x^p\\ | ||
| + | &\equiv& 1+x^p\pmod{p}\end{eqnarray*}</math></center> Assume we have <math>(1+x)^{p^k}\equiv 1+x^{p^k}\pmod{p}</math>. Then <center><math>\begin{eqnarray*}(1+x)^{p^{k+1}} | ||
| + | &\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*}</math></center> | ||
== Links == | == Links == | ||
Revision as of 10:22, 8 November 2007
Let 
be a prime. If 
is the base representation of 
and 
is the base representation of 
, where 
, Lucas' Theorem states that ![\[\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}\]](http://latex.artofproblemsolving.com/6/8/6/686f8a9285e821431a8a874149cd0453652e0495.png)
Contents
Proof
Lemma
For prime and 
,
![\[(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}\]](http://latex.artofproblemsolving.com/8/5/2/8525b740caf0083bea15ba4e378dddd8e302c072.png)
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)
