Math Core

You already know how to count trailing zeros of $n!$ by counting factors of $5$ . Legendre's formula is the general version: it gives the exact power of any prime in $n!$ . With it you can find trailing zeros in any base, the largest power of $12$ dividing $50!$ , and the power of a prime dividing a binomial coefficient. That last one leads to a beautiful fact about which entries of Pascal's triangle are odd.

Legendre's formula

Among $1, 2, \dots, n$ , exactly $\left\lfloor \dfrac{n}{p} \right\rfloor$ are multiples of $p$ , and each contributes at least one factor of $p$ to $n!$ . Exactly $\left\lfloor \dfrac{n}{p^2} \right\rfloor$ are multiples of $p^2$ , and each contributes a second factor. Continue with $p^3, p^4, \dots$ Each number is counted once for every factor of $p$ it has.

Legendre's formula

The exponent of the prime $p$ in $n!$ is

$v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots = \frac{n - s_p(n)}{p - 1},$

where $s_p(n)$ is the sum of the digits of $n$ in base $p$ .

The digit-sum form is a great shortcut for $p = 2$ : $v_2(n!) = n - (\text{number of 1s in the binary form of } n)$ . For instance, $2026 = 11111101010_2$ has eight $1$ s, so $v_2(2026!) = 2026 - 8 = 2018$ .

Trailing zeros in any base

$n!$ ends in $k$ zeros in base $b$ when $b^k$ divides $n!$ but $b^{k+1}$ does not. Factor $b$ into primes; for each prime power $p^e$ in $b$ , the number of copies available is $\left\lfloor \dfrac{v_p(n!)}{e} \right\rfloor$ . The answer is the smallest of these. In base $10$ the bottleneck is always $5$ , but in other bases you must check each prime.

Binomial coefficients

Since $\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ , you get $v_p\dbinom{n}{k} = v_p(n!) - v_p(k!) - v_p((n-k)!)$ . Using the digit-sum form, this simplifies to

$v_p\binom{n}{k} = \frac{s_p(k) + s_p(n - k) - s_p(n)}{p - 1},$

which equals the number of carries when you add $k$ and $n - k$ in base $p$ (Kummer's theorem). In particular, $\dbinom{n}{k}$ is odd exactly when adding $k$ and $n - k$ in binary has no carries, meaning every $1$ in the binary form of $k$ sits where $n$ also has a $1$ . So if $n$ has $m$ ones in binary, exactly $2^m$ entries in row $n$ of Pascal's triangle are odd.

Worked example: A prime in a factorial

What is the largest power of $3$ that divides $100!$ ?

$\left\lfloor \frac{100}{3} \right\rfloor + \left\lfloor \frac{100}{9} \right\rfloor + \left\lfloor \frac{100}{27} \right\rfloor + \left\lfloor \frac{100}{81} \right\rfloor = 33 + 11 + 3 + 1 = 48.$

So $3^{48}$ divides $100!$ but $3^{49}$ does not.

Worked example: Trailing zeros in base 12

How many zeros does $30!$ end in when written in base $12$ ?

$12 = 2^2 \cdot 3$ . Factors of $2$ : $15 + 7 + 3 + 1 = 26$ , enough for $\left\lfloor \dfrac{26}{2} \right\rfloor = 13$ copies of $2^2$ . Factors of $3$ : $10 + 3 + 1 = 14$ . The bottleneck is $2^2$ , so $30!$ ends in $13$ zeros in base $12$ .

Worked example: A power of 2 in a binomial coefficient

What is the largest power of $2$ dividing $\dbinom{100}{50}$ ?

By Legendre, $v_2(100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97$ and $v_2(50!) = 25 + 12 + 6 + 3 + 1 = 47$ . So $v_2\dbinom{100}{50} = 97 - 2 \cdot 47 = 3$ , and the answer is $2^3$ .

With carries: $50 = 110010_2$ has three $1$ s, and adding $50 + 50$ in binary carries exactly once for each of them. Three carries again gives $2^3$ .

Worked example: Odd entries in a row of Pascal's triangle

For how many $k$ with $0 \le k \le 100$ is $\dbinom{100}{k}$ odd?

$100 = 1100100_2$ has three $1$ s. $\dbinom{100}{k}$ is odd exactly when the $1$ s of $k$ are among those three positions, so there are $2^3 = 8$ such $k$ .

Common mistake

For a base like $12 = 2^2 \cdot 3$ , don't just compare $v_2$ and $v_3$ . You need two $2$ s for every $12$ , so divide $v_2$ by $2$ (rounding down) before comparing. Also, don't stop Legendre's sum early: $\left\lfloor \dfrac{n}{p^k} \right\rfloor$ terms keep contributing until $p^k \gt n$ .

Practice

Practice 1

How many zeros are at the end of $2026!$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 2

What is the largest integer $k$ such that $7^k$ divides $500!$ ?

Practice 3

How many zeros does $20!$ end in when written in base $6$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 4

What is the largest integer $k$ such that $12^k$ divides $50!$ ?

Practice 5

What is the smallest positive integer $k$ such that no factorial $n!$ ends in exactly $k$ zeros?

Practice 6

What is the exponent of $3$ in the prime factorization of $\dbinom{200}{100}$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 7

What is the smallest positive integer $n$ such that $2^{100}$ divides $n!$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 8

For how many integers $k$ with $0 \le k \le 255$ is $\dbinom{255}{k}$ odd, and for how many $k$ with $0 \le k \le 256$ is $\dbinom{256}{k}$ odd? Give the sum of the two counts.

Real contest practice

2015 AMC 10B, Problem 23: comparing the trailing zeros of $n!$ and $(2n)!$ .
2017 AMC 12B, Problem 16: the probability that a random divisor of $21!$ is odd, using the power of $2$ in $21!$ .