Number theory Divisibility and primes Theorem

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. 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$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Prime number definition
P-adic valuation definition
Legendre's formula statement

Tag	`01WPV9PHN7`
URI	`m2://01WPV9PHN7`
Aliases	`de-polignac-formula`
Kind	statement, theorem
Writing	W0 stub
MSC	11A51
Status	This copy of the site has no build data. Run `m2 status 01WPV9PHN7`.
Uses	P-adic valuation
Same as	Wikidata Q23041626 Wikipedia Legendre's formula

Legendre's formula

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here