---
tag: 01WPV9PHN7
kind: statement
role: theorem
name: Legendre's formula
aliases: [de-polignac-formula]
msc: [11A51]
uses: [04VCPS30ZE]
sources:
  - url: https://en.wikipedia.org/wiki/Legendre%27s_formula
    locator: Statement
same_as:
  wikidata: Q23041626
  wikipedia: Legendre's formula
---

## Statement

Let $p$ be a prime number and let $n$ be a natural number. Let $\nu_p$ be the [[p-adic valuation|04VCPS30ZE]].
Then
$$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor.$$
The sum is finite, because $\lfloor n / p^i \rfloor = 0$ when $p^i > n$.

## Remarks

An equivalent form: $\nu_p(n!) = \dfrac{n - s_p(n)}{p - 1}$, where $s_p(n)$ is the sum of the digits of $n$ in base $p$.
For example, $\nu_2(10!) = 5 + 2 + 1 = 8$, and $\nu_5(100!) = 20 + 4 = 24$. So $100!$ ends with $24$ zeros.
The proof counts, for each $i$, the multiples of $p^i$ among $1, \dots, n$.

## Explanations

### L1 human

To count the factors $p$ in $n!$, count the multiples of $p$ up to $n$. Then add the multiples of $p^2$, which give a second factor, and so on.
For $10!$ and $p = 3$: there are $3$ multiples of $3$ and $1$ multiple of $9$, so $3^4$ is the largest power of $3$ that divides $10!$.