Let $n\in\mathbb{N}$ and $p$ prime

i) Show $\forall h\in\mathbb{N}$, the number of $m\in\mathbb{Z}$, with $1\leq m\leq n$, divisible by $p^h$ is

equal to $\left[\frac{n}{p^h}\right]$, where $\left[\theta\right]$ denotes the integer part of $\theta$

ii) Hence deduce that the power of $p$ dividing $n!$ is $p^{e_p}$, where $e_p<\frac{n}{p-1}$

I am fine with part (i) so we can assume that answer.

Part (ii)

Answer (ii):

(1) For each $h\in\mathbb{N}$, there are $\left[\frac{n}{p^h}\right]−\left[\frac{n}{p^{h+1}}\right]$ such integers divisible by $p^h$ but not by $p^{h+1}$.

(2) Also, when h is sufficiently large, one has $\left[\frac{n}{p^h}\right]=0$.

(3) Then the largest power of $p$ dividing $n!$, ($e_p$), is: $$\sum_{m=0}^\infty m\left(\left[\frac{n}{p^m}\right]-\left[\frac{n}{p^{m+1}}\right]\right)$$

(4) $$\sum_{m=0}^\infty m\left(\left[\frac{n}{p^m}\right]-\left[\frac{n}{p^{m+1}}\right]\right)=\sum_{m=1}^\infty\left[\frac{n}{p^m}\right]<\sum_{m=1}^\infty\frac{n}{p^m}=\frac{n}{p-1}$$

I understand most of this argument, but am comfused by part (3), why is there an $m$ before the

"$\left(\left[\frac{n}{p^m}\right]-\left[\frac{n}{p^{m+1}}\right]\right)$" part.

Also why do we take the sum of the number of integers divisible by $p^h$ but not by $p^{h+1}$?


Those multiples of $p$ but not $p^2$ each give one power of $p$ to the product.
Those multiples of $p^2$ but not $p^3$ each give two powers of $p$.
Those multiples of $p^3$ but not $p^4$ each give three powers of $p$.
In (3), you have $\lfloor\frac{n}{p^m}\rfloor-\lfloor\frac{n}{p^{m+1}}\rfloor$ factors, each contribute $m$ powers of $p$ to the product.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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