### Theorem: N = [n/p] + [n/p^{2}] + [n/p^{3}] + ...

**Theorem:** Let N be the highest power of p that divides n!.
Then N is the sum

N = [n/p] + [n/p^{2}] + [n/p^{3}] + ...

On our page on division lemmas, we said
that, where p is a prime and a is a natural number not divisible by p, the only
positive multiples of a that are divisible by p are:

a·p, a·2p, a·3p, ... (sequence 1)

Now, let S_{n} be the set of the first n natural numbers. It
follows from the lemma, above, that

the number of elements of S_{n} that are divisible by p is [n/p].

By similar arguments, the following sequence of statements are all true:

the number of elements of S_{n} that are divisible by p^{2}
is [n/p^{2}],

the number of elements of S_{n} that are divisible by p^{3} is
[n/p^{3}],

the number of elements of S_{n} that are divisible by p^{4} is
[n/p^{4}],

etc.

Note that if e_{k} is the exponent of the highest power of p that is
divides k, then e_{k} is also the number of elements of {p, p^{2},
p^{3}, ...} that divide k. Therefore, the sum of all e_{k}
for all the k from 1 to n is the sum of the sums of all the elements of S_{n}
that are divisible by all the powers of p. The sum of all e_{k}
for all the k from 1 to n is the exponent of the highest power of p that divides
n!. That is,

N = [n/p] + [n/p^{2}] + [n/p^{3}] + ...

which proves the theorem.

### Internet references

### Related pages in this website

Counting Primes method of proving the
following are integers: C(n,k) = n!/(k!(n-k)!), (2a)!(2b)!/((a+b)!a!b!)

Combination identities proves the
standard combination identities, including C(n,k) = C(n-1,k-1) + C(n-1,k) and
many others.

Floor Function Identities,
which are used in proofs that combinatorial identities are integers

The webmaster and author of this Math Help site is
Graeme McRae.