Difference between revisions of "Lucas' Theorem"

Revision as of 14:26, 8 November 2007

Let $p$ be a prime. 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$ , Lucas' Theorem states that $\binom{n}{i}\equiv \prod_{j=0}^{m}\binom{n_j}{i_j}\pmod{p}$

Proof

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 that

$

\begin{array}{rcl} (1 + x)^{p} & \equiv & (\binom{p}{0}) + (\binom{p}{1}) x + (\binom{p}{2}) x^{2} + \dots + (\binom{p}{p - 1}) x^{p - 1} + (\binom{p}{p}) x^{p} \\ \equiv & 1 + x^{p} (\mod p) \end{array}

$ (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)

@@ Line 19: / Line 19: @@
 * [[Combinatorics]]
 * [[Generating function]]
+[[Category:Theorems]]

Page

Toolbox

Search

Difference between revisions of "Lucas' Theorem"

Revision as of 14:26, 8 November 2007

Contents

Proof

Lemma

Proof

Links

See also