Determining the Prime Order of a Prime Power Factorial

108 Views Asked by At

Let $\text{ord}_p{(n)}$ denote the largest power of $p$ that divides $n$. Thus for example,

$$\text{ord}_5{(250)}=\text{ord}_5{\left(2\cdot 5^3\right)}=3$$

I want show that for a fixed $N$ and $p$, that

$$\text{ord}_p{\left[\left(p^N\right)!\right]}=1+p+p^2+...+p^{N-1}$$

As the order of a prime works like a logarithm i know i can rewrite as

$$\text{ord}_p{\left[\left(p^N\right)!\right]}=\sum_{k=1}^{p^N}\text{ord}_p{(k)}$$

Now, only multiples of $p$ have $\text{ord}_p{(k)}>0.$ Thus, if a number is not a multiple of $p$ its order is $0$. Thus, we can rewrite as

\begin{eqnarray*}\sum_{k=1}^{p^N}\text{ord}_p{(k)}&=&\sum_{k=1}^{p^{N-1}}\text{ord}_p{(pk)}\\&=&\sum_{k=1}^{p^{N-1}}\left[\text{ord}_p(p)+\text{ord}_p{(k)}\right]\\&=&\sum_{k=1}^{p^{N-1}}1+\sum_{k=1}^{p^{N-1}}\text{ord}_p(k)\\&=&p^{N-1}+\text{ord}_p{\left[\left(p^{N-1}\right)!\right]}\end{eqnarray*}

This gives the recurrence relation

$$\text{ord}_p{\left[\left(p^N\right)!\right]}=p^{N-1}+\text{ord}_p{\left[\left(p^{N-1}\right)!\right]}$$

and so

\begin{eqnarray*}\text{ord}_p{\left[\left(p^N\right)!\right]}&=&p^{N-1}+\text{ord}_p{\left[\left(p^{N-1}\right)!\right]}\\&=&p^{N-1}+p^{N-2}+\text{ord}_p{\left[\left(p^{N-2}\right)!\right]}\\&=&p^{N-1}+p^{N-2}+p^{N-3}\text{ord}_p{\left[\left(p^{N-3}\right)!\right]}\\&=&...\\&=&p^{N-1}+p^{N-2}+...+p+1\end{eqnarray*}

Now, my question is, is there an easier way to see this result? Is there a quicker way to obtain the same result?