# 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).

Title Lucas’s theorem LucassTheorem 2013-03-22 13:17:31 2013-03-22 13:17:31 mathcam (2727) mathcam (2727) 6 mathcam (2727) Theorem msc 11B65