Difference between revisions of "Lucas' Theorem"

Latest revision as of 14:13, 11 August 2020

Lucas' Theorem states that for any prime $p$ and any positive integers $n\geq i$ , if $(\overline{n_mn_{m-1}\cdots n_0})_p$ is the representation of $n$ in base $p$ and $(\overline{i_mi_{m-1}\cdots i_0})_p$ is the representation of $i$ in base $p$ (possibly with some leading $0$ s) 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*}$ 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*}$

@@ 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> 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> in base <math>p</math> (possibly with some leading <math>0</math>s) then <math>\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}</math>.
-== Proof ==
+== Lemma ==
-=== 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>
+<center><math>(1+x)^{p^r}\equiv 1+x^{p^r}\pmod{p}</math></center>
 === 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}}
+<cmath>\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*}</cmath>
+Assume we have <math>(1+x)^{p^k}\equiv 1+x^{p^k}\pmod{p}</math>. Then
+<cmath>\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>
+&\equiv&1+x^{p^{k+1}}\pmod{p}\end{eqnarray*}</cmath>
-== Links ==
 == See also ==
 * [[Combinatorics]]
 * [[Generating function]]
+* [[Binomial Theorem]]
 [[Category:Theorems]]
+[[Category:Number theory]]

Page

Toolbox

Search

Difference between revisions of "Lucas' Theorem"

Latest revision as of 14:13, 11 August 2020

Lemma

Proof

See also