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

The $p$ -adic valuation $v_p(n)$ is the exponent of prime $p$ in $n$ ’s prime factorization — how many times $p$ divides $n$ . This lesson is about computing $v_p(n!)$ , which shows up constantly in “how many trailing zeros” and “highest power of a prime dividing this factorial” problems.

Legendre’s formula

v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \dfrac{n}{p^k} \right\rfloor = \left\lfloor\dfrac np\right\rfloor + \left\lfloor\dfrac{n}{p^2}\right\rfloor + \left\lfloor\dfrac{n}{p^3}\right\rfloor + \cdots

The sum is finite in practice — once $p^k > n$ , that term (and every later one) is zero, so you just stop once the floor becomes 0.

Trailing zeros

A trailing zero in $n!$ comes from a factor of 10, i.e. a pair of factors 2 and 5. Since factors of 2 are far more abundant than factors of 5 in any factorial, the number of trailing zeros is limited entirely by $v_5(n!)$ — you only ever need to apply Legendre’s formula with $p=5$ .

Worked example

Problem: How many trailing zeros does $100!$ have?

Solution: Compute $v_5(100!)$ :

\left\lfloor\dfrac{100}{5}\right\rfloor + \left\lfloor\dfrac{100}{25}\right\rfloor + \left\lfloor\dfrac{100}{125}\right\rfloor = 20+4+0 = 24

So $100!$ ends in 24 zeros.

Practice problems

1.Find $v_2(20!)$ .

2.How many trailing zeros does $50!$ have?

3.Find the largest power of 3 dividing $30!$ .

4.Why does $100!$ end in exactly 24 zeros rather than needing to check factors of 2 as well?

Factorization & Valuation

Legendre’s formula

Trailing zeros

Practice problems