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.

I had came across a theorem a few weeks ago and I tried to make sense of it but could not at the time, so I put it down and recently picked it back up to take another shot, but the thing is, what I think this problem might involve I am not very familiar with in mathematical terms. I use it for programming when needed, being the (floor function) but not have had anything experiences mathematically. I would like to see how this problem is approached by mean of a mathematical induction but not literally "induction" if not needed.

The theorem is posed as so: $$ \mathrm{e_p}(n!) = \sum_{r\ge 1} \! \left\lfloor\frac{n}{p^r}\right\rfloor $$

Feel free to use any method, none in particular was in question of going about showing the above formula.

Thanks

share|improve this question

1 Answer 1

up vote 4 down vote accepted

$e_p$ means the exponent of the prime number $p$ in the decomposition of $n!$. You can think of it as follows: $n!=1\cdot 2\cdot...\cdot n$. There are $\lfloor \frac{n}{p}\rfloor$ numbers divisible by $p$ in this product. But this number does not reflect the exponent of $p$ because there are some numbers which are divisible by $p^2$. We count those as being $\lfloor \frac{n}{p^2}\rfloor$.

In general, there are $\lfloor \frac{n}{p^k}\rfloor$ numbers divisible by $p^k$ in the given product. Therefore, to find the total exponents it is enough to sum $\sum_{k \geq 1}\lfloor \frac{n}{p^k}\rfloor$. The reasoning is like this. Count the numbers divisible by $p$ and add the answer to the exponent. Count the numbers divisible by $p^2$ and add the answer to the previous result. ... Count the numbers divisible by $p^k$ and add the answer to the previous result. Note that this process will stop once $p^k>n$.

share|improve this answer
    
Oh, what a simple notation. I had thought that might be the case, but I would be very embarrassed if I was notationally wrong. –  mixedmath Jun 1 '11 at 10:19
    
Thanks, now it much clearer too see. Thanks for that quite elementary explanation. –  night owl Jun 1 '11 at 15:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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