Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Lucas' Theorem"

m (Needs to be wikified -- internal links, etc.)
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>
+
'''Lucas' Theorem''' states that for any [[prime]] <math>p</math> , 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>, then <math>\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}</math>.
  
 
== Lemma ==
 
== Lemma ==
Line 5: Line 5:
 
<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>
 
=== Proof ===
 
=== 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\\
+
For all <math>1\leq k \leq p-1</math>, <math>\binom{p}{k}\equiv 0 \pmod{p}</math>. Then we have
−
&\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}}
+
<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&\left(1+x^{p^k}\right)^p\\
 
&\equiv&\left(1+x^{p^k}\right)^p\\
Line 13: Line 16:
  
 
== Proof ==
 
== 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}\\
+
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
 +
<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}\\
 
&=&[(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*}</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>.
+
\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>.
  
−
== Example ==
+
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>.
  
−
== Links ==
+
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>.
  
 
== See also ==
 
== See also ==
−
 
 
* [[Combinatorics]]
 
* [[Combinatorics]]
 
* [[Generating function]]
 
* [[Generating function]]
Line 30: Line 36:
 
[[Category:Number theory]]
 
[[Category:Number theory]]
 
[[Category:Theorems]]
 
[[Category:Theorems]]
−
 
−
{{wikify}}
 

Revision as of 20:31, 21 April 2008

Lucas' Theorem states that for any prime $p$ , if $(\overline{n_mn_{m-1}\cdots n_0})_p$ is the base $p$ representation of $n$ and $(\overline{i_mi_{m-1}\cdots i_0})_p$ is the base $p$ representation of $i$, where $n\geq i$, then $\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}$.

Lemma

For $p$ prime and $x,r\in\mathbb{Z}$, \[(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}\]

Proof

For all $1\leq k \leq p-1$, $\binom{p}{k}\equiv 0 \pmod{p}$. Then we have

$\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*}$ (Error compiling LaTeX. Unknown error_msg)

Assume we have $(1+x)^{p^k}\equiv 1+x^{p^k}\pmod{p}$. Then

$\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*}$ (Error compiling LaTeX. Unknown error_msg)

Proof

Consider $(1+x)^n$. If $(\overline{n_mn_{m-1}\cdots n_0})_p$ is the base $p$ representation of $n$, then $0\leq n_k \leq p-1$ for all $0\leq k \leq m$ and $n=n_mp^m+n_{m-1}p^{m-1}+\cdots+n_1p+n_0$. We then have

$\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*}$ (Error compiling LaTeX. Unknown error_msg)

We want the coefficient of $x^i$ in $(1+x)^n$. Since $i=i_mp^m+i_{m-1}p^{m-1}+\cdots+i_1p+i_0$, we want the coefficient of $(x^{p^{m}})^{i_{m}}(x^{p^{m-1}})^{i_{m-1}}\cdots (x^p)^{i_1}x^{i_0}$.

The coefficient of each $(x^{p^{k}})^{i_{k}}$ comes from the binomial expansion of $(1+x^{p^k})^{n_k}$, which is $\binom{n_k}{i_k}$. Therefore we take the product of all such $\binom{n_k}{i_k}$, and thus we have

$\binom{n}{i}\equiv\prod_{k=1}^{n}\binom{n_k}{i_k}\pmod{p}$

Note that $n_k<i_k\Longrightarrow\binom{n_k}{i_k}=0\Longrightarrow\binom{n}{i}\equiv 0 \pmod{p}$.

This is equivalent to saying that there is no $x^i$ term in the expansion of $(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}$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Lucas%27_Theorem&oldid=25125"