Lucas' theorem

From Wikipedia, the free encyclopedia

For the theorem in complex analysis, see Gauss-Lucas theorem.

Lucas theorem first appeared in 1878 in Edouard Lucas, Thkorie des Functions Numtriques Simplement Periodiques, American J. Math., 1 (1878), 184-240, 289-321.

In number theory, the Lucas' theorem states the following: Let m and n be non-negative integers and p a prime. Let

m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0, and
n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0

be the base p expansions of m and n respectively. Then

\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p.

where \binom{m}{n}=\frac{m!}{n!(m-n)!} denotes the binomial coefficient of m and n, also known as "m choose n".


[edit] External links

This number theory-related article is a stub. You can help Wikipedia by expanding it.