## You are here

HomeLucas's theorem

## Primary tabs

# Lucas’s theorem

Let $m,n\in\mathbb{N}-\{0\}$ be two natural numbers . If $p$ is a prime number and :

$m=a_{k}p^{k}+a_{{k-1}}p^{{k-1}}+\cdots+a_{1}p+a_{0},n=b_{k}p^{k}+b_{{k-1}}p^{{% k-1}}+\cdots+b_{1}p+b_{0}$ |

are the base-p expansions of $m$ and $n$ , then the following congruence is true :

${m\choose n}\equiv{a_{0}\choose b_{0}}{a_{1}\choose b_{1}}\cdots{a_{k}\choose b% _{k}}(\verb|modp|)$ |

Note : the binomial coefficient is defined in the usual way , namely :

${x\choose y}=\frac{x!}{y!(x-y)!}$ |

if $x\geq y$ and $0$ otherwise (of course , x and y are natural numbers).

Keywords:

binomial coefficient,congruence

Type of Math Object:

Theorem

Major Section:

Reference

Groups audience:

## Mathematics Subject Classification

11B65*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff

## Recent Activity

Apr 15

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier

new question: Prove a formula is part of the Gentzen System by LadyAnne

Mar 30

new question: A problem about Euler's totient function by mbhatia

new problem: Problem: Show that phi(a^n-1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia

new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz

Mar 26

new correction: Misspelled name by DavidSteinsaltz

Mar 21

new correction: underline-typo by Filipe

Mar 19

new correction: cocycle pro cocyle by pahio

Mar 7

new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier

new image: expected waiting time by robert_dodier

new image: plot W(t) = P(waiting time <= t) by robert_dodier

## Comments

## On Lucas's Theorem

Hi, Slash,

think you were not quite precise in your statement. Consider this:

Let $m,n$ be natural numbers, $m \ge n$ and $p$ a prime number dividing both

$m$ and $n$. Then you have

\[{m \choose n} =\frac{m^{'}.(m -1)\cdots (m -(n -1))}{p^s.n^{'}(n -1)\cdots

1}\]

where $r,s$ are the maximum powers of $p$ dividing $m$ and $n$. But then the

binomial coefficient would be $0 \bmod p$, but ${0 \choose 0} =1$ so in this

case the theorem is wrong.

I'm sure I found this theorem in a paper about binomial coefficients,

written by Andrew Granville. This paper sure also contains a proof of

this...

Regards,

Thomas

## Re: On Lucas's Theorem

If r>s , then the number of zeros at the end in the p-base expansion of m is greater than the one in the expansion of n , so you would get that the product is zero ! (a term of the form {0 \choose something} appears!) So .. the theorem is true in this case (correct me if I'm wrong)! I have a proof of it but I didn't have time to write it up in LaTeX .

Cheers !

P.S. : I hope I'm not talking nonsense and that it's correct