---
tag: 0RY4GGMEQG
kind: statement
role: theorem
name: Lucas's theorem
msc: [11B65]
uses: [0TPW25CBN6, 0SN0MAEKYX]
sources:
  - url: https://en.wikipedia.org/wiki/Lucas%27s_theorem
    locator: Statement
same_as:
  wikidata: Q1186808
  wikipedia: Lucas's theorem
---

## Statement

Let $p$ be a [[prime number|0SN0MAEKYX]], and let $m$ and $n$ be natural numbers with base-$p$ digits $m = \sum_{i=0}^{k} m_i p^i$ and $n = \sum_{i=0}^{k} n_i p^i$, where $0 \le m_i, n_i < p$.
Then
$$\binom{m}{n} \equiv \prod_{i=0}^{k} \binom{m_i}{n_i} \pmod p,$$
with the convention $\binom{a}{b} = 0$ when $b > a$.

## Remarks

A consequence: $p \mid \binom{m}{n}$ if and only if $n_i > m_i$ for some digit $i$.
For example, with $p = 3$: $10 = 101_3$ and $4 = 011_3$. The theorem gives $\binom{10}{4} \equiv \binom{1}{0} \binom{0}{1} \binom{1}{1} = 0 \pmod 3$, and indeed $\binom{10}{4} = 210$.
For $p = 2$, the binomial coefficient $\binom{m}{n}$ is odd if and only if $m$ has a binary digit $1$ at each place where $n$ has one.

## History

Édouard Lucas published the theorem in 1878.

## Explanations

### L1 human

To find a binomial coefficient modulo a prime $p$, write both numbers in base $p$.
Then compute small binomial coefficients digit by digit and multiply them.
This explains the pattern of odd numbers in Pascal's triangle, which looks like the Sierpiński triangle.