Highest power of a prime $p$ dividing $N!$

Largest power of a prime dividing $N!$

In general, the highest power of a prime $p$ dividing $N!$ is given by

$$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

The first term appears since you want to count the number of terms less than $N$ and are multiples of $p$ and each of these contribute one $p$ to $N!$. But then when you have multiples of $p^2$ you are not multiplying just one $p$ but you are multiplying two of these primes $p$ to the product. So you now count the number of multiple of $p^2$ less than $N$ and add them. This is captured by the second term $\displaystyle \left \lfloor \frac{N}{p^2} \right \rfloor$. Repeat this to account for higher powers of $p$ less than $N$.

Number of zeros at the end of $N!$

The number of zeros at the end of $N!$ is given by $$\left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor + \cdots$$ where $\left \lfloor \frac{x}{y} \right \rfloor$ is the greatest integer $\leq \frac{x}{y}$.

To make it clear, write $N!$ as a product of primes $N! = 2^{\alpha_2} 3^{\alpha_2} 5^{\alpha_5} 7^{\alpha_7} 11^{\alpha_{11}} \ldots$ where $\alpha_i \in \mathbb{N}$.

Note that $\alpha_5 < \alpha_2$ whenever $N \geq 2$. (Why?)

The number of zeros at the end of $N!$ is the highest power of $10$ dividing $N!$

If $10^{\alpha}$ divides $N!$ and since $10 = 2 \times 5$, $2^{\alpha} | N!$ and $5^{\alpha} | N!$. Further since $\alpha_5 < \alpha_2$, the highest power of $10$ dividing $N!$ is the highest power of $5$ dividing $N!$ which is $\alpha_5$.

Note that there will be 

 1. A jump of $1$ zero going from $(N-1)!$ to $N!$ if $5 \mathrel\| N$

 2. A jump of $2$ zeroes going from $(N-1)!$ to $N!$ if $5^2 \mathrel\| N$

 3. A jump of $3$ zeroes going from $(N-1)!$ to $N!$ if $5^3 \mathrel\| N$ and in general

 4. A jump of $k$ zeroes going from $(N-1)!$ to $N!$ if $5^k \mathrel\| N$

where $a \mathrel\| b$ means $a$ divides $b$ and $\gcd\left(a,\dfrac{b}{a} \right)$ = 1.

Largest power of a prime dividing other related products

In general, if we want to find the highest power of a prime $p$ dividing numbers like $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$, $\displaystyle P(N,r)$, $\displaystyle \binom{N}{r}$, the key is to write them in terms of factorials.

For instance, $$\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1) = \frac{(2N)!}{2^N N!}.$$ Hence, the largest power of a prime, $p>2$, dividing $\displaystyle 1 \times 3 \times 5 \times \cdots \times (2N-1)$ is given by $s_p((2N)!) - s_p(N!)$, where $s_p(N!)$ is defined above. If $p = 2$, then the answer is $s_p((2N)!) - s_p(N!) - N$.

Similarly, $$\displaystyle P(N,r) = \frac{N!}{(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle P(N,r)$ is given by $s_p(N!) - s_p((N-r)!)$, where $s_p(N!)$ is defined above.

Similarly, $$\displaystyle C(N,r) = \binom{N}{r} = \frac{N!}{r!(N-r)!}.$$ Hence, the largest power of a prime, dividing $\displaystyle C(N,r)$ is given by $$s_p(N!) - s_p(r!) - s_p((N-r)!)$$ where $s_p(N!)$ is defined above.

For a number $n$, define $\Lambda(n)=\log p$ if $n=p^k$ and zero elsewhen.

Note that $\log n=\sum\limits_{d\mid n}\Lambda(d)$. If $N=n!$, then $$\log N=\sum_{k=1}^n\log k=\sum_{k=1}^n\sum_{d\mid k}\Lambda (d)=\sum_{d=1}^n \Lambda(d)\left\lfloor \frac nd\right\rfloor$$

Since $\Lambda(d)$ is nonzero precisely when $d$ is a power of a prime and in such case it equals $\log p$, the last sum equals $$\sum_{p}\sum_{k\geqslant 1}\log p \left\lfloor\frac n{p^k}\right\rfloor$$ and this gives $$\nu_p(n!)=\sum_{k\geqslant 1}\left\lfloor\frac n{p^k}\right\rfloor$$ If you write $n$ is base $p$, say $n=a_0+a_1p+\cdots+a_kp^k$, the above gives that $$\nu_p(n!)=\frac{s(n)-n}{1-p}$$ where $s(n)=a_0+\cdots+a_k$.

de Polignac's formula named after Alphonse de Polignac, gives the prime decomposition of the factorial $n!$.