Exercise 928Number theory › Divisibility and gcdL1Added 3 Nov 2026

Prime power divisibility

#prime power#valuation#p-adic

Statement

Let $p$ be prime and $n\ge1$ . Show that the exponent of $p$ in $n!$ is
$v_p(n!)=\sum_{k\ge1}\left\lfloor\frac{n}{p^k}\right\rfloor.$

Hint

Count multiples of $p$ , then of $p^2$ , etc. Multiples of $p^k$ each contribute at least $k$ to the exponent.

Show solutionHide solution

Solution

Counting. Among $1,\ldots,n$ , the number of multiples of $p$ is $\lfloor n/p\rfloor$ ; multiples of $p^2$ is $\lfloor n/p^2\rfloor$ ; etc.

Sum. The exponent of $p$ in $n!$ is the sum over $k\ge1$ of the number of multiples of $p^k$ , since a multiple of $p^k$ contributes $k$ to the exponent (counted once for $p$ , once for $p^2$ , ..., once for $p^k$ ).

Conclusion. $v_p(n!)=\sum_{k\ge1}\lfloor n/p^k\rfloor$ .

Example. $v_2(10!)=\lfloor10/2\rfloor+\lfloor10/4\rfloor+\lfloor10/8\rfloor=5+2+1=8$ .

Prime power divisibility

Statement

Solution

More problems in Divisibility and gcd