3
$\begingroup$

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

1 Answers 1

4

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

  • 0
    Thanks, now it much clearer too see. Thanks $f$or that quite elementary explanation.2011-06-01