Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Highest power of a prime $p$ dividing $N!$

How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?

share|improve this question

marked as duplicate by Marvis, Aryabhata, Qiaochu Yuan May 5 '12 at 19:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4  
+1 for this very interesting observation. –  Arjang Jan 18 '11 at 1:38
3  
Question title should be edited imo –  Louis Rhys Jan 18 '11 at 5:03
    
@Marvis: If we close this one, perhaps we don't need this to be the generalized question... –  Aryabhata May 5 '12 at 7:05
    
@Aryabhata I followed Bill's suggestion in the comments to my answer. I have hence created a new question with the answer. Bill "The problem with changing a very specific question like this to a more general one is that it makes some of the other answers look confused, wrong, etc. Thus it would be better to post a new more general question and link the more specific questions to the general one (and vice versa)." –  user17762 May 5 '12 at 7:18
    
@Marvis: Then you should revert the edits made to this question (which I see you did), and remove the tag faq (which you see I did :-)). We can still close it as dupe. Normally one would expect questions to be closed as dupes of older questions, not newer ones. But the software allows it... Don't forget to update the list on meta with the parent question. –  Aryabhata May 5 '12 at 17:07
add comment

3 Answers 3

up vote 30 down vote accepted

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$, $\forall N$. (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$.

So you will find that for $N \leq 24$, the number of zeros will be less than or equal to 4. However when $N$ hits $25$ you will get 2 additional zeros courtesy $25$ since $25 \times 2^2 = 100$. Hence, there will be a jump when you go from $24$ to $25$.

EDIT:

Note that there will be

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

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

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

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

where $a || b$ means $a$ divides $b$ and gcd($a,\frac{b}{a}$) = 1

EDIT

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$.

In case of the current example, the largest prime dividing $10$ is $5$. Hence, the largest power of $10$ dividing $N!$ is the same as the largest power of $5$ dividing $N!$.

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 (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 (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 (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.

share|improve this answer
    
sorry but i don't understand what you are trying to say. –  user5962 Jan 17 '11 at 23:42
4  
The number of zeros is the number of factors of 5 in N!, as there are plenty of 2's. How many 5's are in 24!? It is 4, as you get one each from 5, 10, 15, and 20. How many are in 25!? 6, because you got two more from 25. This is just what the expression above is telling you. –  Ross Millikan Jan 17 '11 at 23:44
    
thank you very much! –  user5962 Jan 18 '11 at 0:05
    
Does this also mean that N! cannot terminate in more than 6 zeros? –  Sev Feb 19 '11 at 9:06
    
@Sev: $N!$ will end with $7$ zeros when $30 \leq N <35$. $N!$ will end with $8$ zeros when $35 \leq N <40$. $N!$ will end with $9$ zeros when $40 \leq N <45$. $N!$ will end with $10$ zeros when $45 \leq N <50$. $N!$ will end with $12$ zeros when $50 \leq N <55$. and so on... –  user17762 Feb 19 '11 at 9:19
show 4 more comments

To answer that, you have to find the jump point from 4 to 6 zeros. The first is at 5!, the second at 10!, the third at 15!, and the forth at 20!. The next point is at 25!. What happens there is, you're multiplying by 5*5, which will multiply with 2 even numbers, and add 2 more zeros.

share|improve this answer
    
thank you very much! –  user5962 Jan 18 '11 at 0:06
1  
One should emphasize that this argument depends crucially on the primality of 5 - see my answer. –  Bill Dubuque Jan 18 '11 at 7:34
add comment

HINT $\: $ The power of a prime $\rm\:p\:$ dividing $\rm\ n!\:$ jumps from $\rm\: p-1\:$ for $\rm\: n = p^2-1\:$ to $\rm\: p+1\: $ for $\rm\: n = p^2\:$ since their are $\rm\:p-1\:$ naturals $\rm < p^2\ $ divisible by $\rm\:p\:,\:$ viz. $\rm\ p,\ 2\:p,\:\cdots\:,\: (p-1)\:p\:.\ $ Now put $\rm\ p = 5\:.$

share|improve this answer
    
@Downvoter: if something is not clear then please feel free to ask questions and I am happy to elaborate. –  Bill Dubuque May 5 '12 at 2:21
    
I don't know, all the $p$s got me a little dizzy. Now I get it. Maybe you could be explicity on the factorization of $n!$ into primes since from there one might see easier that $p^{p-1}$ follows from your assertion. –  Pedro Tamaroff May 5 '12 at 3:07
    
@Peter Yes, I mean the maximal power of p that divides n! The point is that this count of p's in n! bumps up by 2 (vs. 1) once you reach $\rm\:n = p^2,\:$ because it contributes two p's to n! –  Bill Dubuque May 5 '12 at 3:11
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.