How does one find the highest power of a prime p that divides N! and other related products?

Related question: How many zeros are there at the end of N!?

This is being done to reduce abstract duplicates. See

Coping with *abstract* duplicate questions. and List of Generalizations of Common Questions for more details.

**Answer**

**Largest power of a prime dividing N!**

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

sp(N!)=⌊Np⌋+⌊Np2⌋+⌊Np3⌋+⋯

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 p2 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 p2 less than N and add them. This is captured by the second term ⌊Np2⌋. 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 ⌊N5⌋+⌊N52⌋+⌊N53⌋+⋯ where ⌊xy⌋ is the greatest integer ≤xy.

To make it clear, write N! as a product of primes N!=2α23α25α57α711α11… where αi∈N.

Note that α5<α2 whenever N≥2. (Why?)

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

If 10α divides N! and since 10=2×5, 2α|N! and 5α|N!. Further since α5<α2, the highest power of 10 dividing N! is the highest power of 5 dividing N! which is α5.

Note that there will be

1. A jump of 1 zero going from (N−1)! to N! if 5‖

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.

**Attribution***Source : Link , Question Author : Community , Answer Author :
6 revs, 3 users 86%user17762
*