Unipal Initiative - Free Competition Math Courses, From Students For Students

Valuation of a binomial coefficient

Since $\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$ , its prime valuation is just a difference of three Legendre’s-formula computations:

v_p\!\left(\binom{n}{k}\right) = v_p(n!) - v_p(k!) - v_p((n-k)!)

A useful shortcut (Kummer’s theorem) restates this combinatorially: $v_p\binom nk$ equals the number of “carries” when adding $k$ and $n-k$ in base $p$ .

Lucas’s theorem

For a prime $p$ , Lucas’s theorem finds $\binom nk \bmod p$ by working in base $p$ : write $n$ and $k$ in base $p$ as digit sequences $n_i$ and $k_i$ , then:

\binom{n}{k} \equiv \prod_i \binom{n_i}{k_i} \pmod p

with the convention $\binom{n_i}{k_i} = 0$ whenever $k_i > n_i$ . This turns a potentially enormous binomial coefficient into a product of small, easy binomial coefficients on individual base- $p$ digits.

Worked example

Problem: Find $\binom{10}{3} \bmod 2$ using Lucas’s theorem.

Solution: Write 10 and 3 in base 2: $10 = 1010_2$ , $3 = 0011_2$ . Compare digit by digit (from most to least significant): $\binom10,\binom01,\binom11,\binom01$ .

The second factor is $\binom{0}{1}=0$ (since $k_i > n_i$ ), so the whole product is 0.

So $\binom{10}{3} \equiv 0 \pmod 2$ — i.e. $\binom{10}{3}=120$ is even, which checks out directly.

Practice problems

1.Find $v_2\left(\binom84\right)$ using Legendre’s formula on $8!, 4!, 4!$ .

2.Use Lucas’s theorem to determine whether $\binom{6}{2}$ is odd or even (work mod 2).

3.Is $\binom{9}{5}$ odd or even? Use Lucas’s theorem base 2.

4.How many entries in row $n=15$ of Pascal’s triangle are odd? (Hint: $15$ in base 2 is $1111$ .)

Binomial Coefficients & Number Theory

Valuation of a binomial coefficient

Lucas’s theorem

Practice problems