Highest power of a prime pp dividing N!N!

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 αiN.

Note that α5<α2 whenever N2. (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 (N1)! 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

Leave a Comment