Legendre's theorem

Theorem (Legendre)

Let pp be a prime number and let n∈Nn\in\mathbb{N}. Then

vp(n!)=∑k=1∞⌊npk⌋,v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor,

where vp(m)v_p(m) denotes the exponent of pp in the prime factorization of the positive integer mm.

Proof

For every positive integer mm, let vp(m)v_p(m) denote the unique non-negative integer satisfying

pvp(m)∣m,pvp(m)+1∤m.p^{v_p(m)}\mid m, \qquad p^{v_p(m)+1}\nmid m.

Since

n!=∏i=1ni,n! = \prod_{i=1}^{n} i,

the uniqueness of prime factorization implies

vp(n!)=∑i=1nvp(i).(1)v_p(n!) = \sum_{i=1}^{n}v_p(i). \tag{1}

Therefore, it suffices to compute the right-hand side.

For each positive integer ii, observe that

vp(i)=∑k=1∞1pk∣i,(2)v_p(i) = \sum_{k=1}^{\infty} \mathbf{1}_{p^k\mid i}, \tag{2}

where

1pk∣i={1,if pk∣i,0,otherwise.\mathbf{1}_{p^k\mid i} = \begin{cases} 1,&\text{if }p^k\mid i,\\ 0,&\text{otherwise}. \end{cases}

Indeed, if vp(i)=ev_p(i)=e, then

p,p2,…,pep,p^2,\ldots,p^e

divide ii, whereas

pe+1,pe+2,…p^{e+1},p^{e+2},\ldots

do not divide ii. Hence exactly the first ee terms of the series (2) are equal to 11, and every remaining term is 00. Therefore,

∑k=1∞1pk∣i=e=vp(i).\sum_{k=1}^{\infty} \mathbf{1}_{p^k\mid i} = e = v_p(i).

Substituting (2) into (1) yields

vp(n!)=∑i=1n∑k=1∞1pk∣i.(3)v_p(n!) = \sum_{i=1}^{n} \sum_{k=1}^{\infty} \mathbf{1}_{p^k\mid i}. \tag{3}

Since

1pk∣i=0whenever pk>n,\mathbf{1}_{p^k\mid i}=0 \qquad \text{whenever } p^k>n,

every summand in (3) is eventually zero. Consequently, the double sum contains only finitely many non-zero terms, so the order of summation may be exchanged:

vp(n!)=∑k=1∞∑i=1n1pk∣i.(4)v_p(n!) = \sum_{k=1}^{\infty} \sum_{i=1}^{n} \mathbf{1}_{p^k\mid i}. \tag{4}

Fix k≥1k\ge1.

The inner sum

∑i=1n1pk∣i\sum_{i=1}^{n} \mathbf{1}_{p^k\mid i}

counts precisely the integers

i∈{1,…,n}i\in\{1,\ldots,n\}

that are divisible by pkp^k.

Such integers are exactly

pk,2pk,3pk,…,⌊npk⌋pk,p^k, 2p^k, 3p^k, \ldots, \left\lfloor\frac{n}{p^k}\right\rfloor p^k,

and there are

⌊npk⌋\left\lfloor \frac{n}{p^k} \right\rfloor

of them. Hence

∑i=1n1pk∣i=⌊npk⌋.(5)\sum_{i=1}^{n} \mathbf{1}_{p^k\mid i} = \left\lfloor \frac{n}{p^k} \right\rfloor. \tag{5}

Substituting (5) into (4), we obtain

vp(n!)=∑k=1∞⌊npk⌋.v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor.

Finally, if

k>log⁡pn,k>\log_p n,

then pk>np^k>n, and therefore

⌊npk⌋=0.\left\lfloor \frac{n}{p^k} \right\rfloor = 0.

Thus only finitely many terms of the series are non-zero, so the above expression is well defined.

This completes the proof.

□\square