Suppose $ n=a_0+a_1p+\cdots+a_kp^k\qquad 0\leq a_i is the base $p$ (for $p$ a prime) representation of an integer $n$. I'm trying to prove to myself that $ ord_p(n!)=\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1}). $ I know the formula that $\displaystyle ord_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\cdots$. Substituting the representation of $n$ base $p$, I find something like $ \left\lfloor\frac{a_0}{p}+a_1+\cdots a_kp^{k-1}\right\rfloor+\cdots+\left\lfloor\frac{a_0}{p^k}+\cdots+\frac{a_{k-1}}{p}+a_k\right\rfloor+\left\lfloor\frac{a_0}{p^{k+1}}+\cdots+\frac{a_k}{p}\right\rfloor+\cdots $ Pulling out the integer terms, this can be rewritten as $ \left\lfloor\frac{a_0}{p}\right\rfloor+\cdots+\left\lfloor\frac{a_0}{p^{k+1}}+\cdots+\frac{a_k}{p}\right\rfloor+\cdots+\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1}). $ So I have the formula I want at the right, and it amounts to showing that all the terms on the left are actually $0$. For instance, it's clear $\left\lfloor\frac{a_0}{p}\right\rfloor=0$, but I don't know what to do for the other terms. For $\left\lfloor\frac{a_0}{p^2}+\frac{a_1}{p}\right\rfloor$, I can only bound $ \frac{a_0}{p^2}+\frac{a_1}{p}=\frac{a_0+a_1p}{p^2}\leq\frac{p+p^2}{p^2} $ which doesn't give anything conclusive. How can one conclude the leftmost terms are all $0$ to get the alternative formula? Edit: I wouldn't mind seeing the alternative with induction on $n$ instead if it's less messy.
Why does $\mathrm{ord}_p(n!)=\sum_{i=1}^k a_i(1+p+\cdots+p^{i-1})$?.
-
0Think about adding $1$ in base $p$ and looking carefully at carries. – 2012-06-08
2 Answers
EDIT: It appears the main point of confusion relates to these: $ \left\lfloor \frac{a_0}{p^2} + \frac{a_1}{p} \right\rfloor \leq \left\lfloor \frac{p-1}{p^2} + \frac{p-1}{p} \right\rfloor = \left\lfloor \frac{p^2-1}{p^2} \right\rfloor = 0.$ $ \left\lfloor \frac{a_0}{p^3} + \frac{a_1}{p^2} + \frac{a_2}{p} \right\rfloor \leq \left\lfloor \frac{p-1}{p^3} + \frac{p-1}{p^2} + \frac{p-1}{p} \right\rfloor = \left\lfloor \frac{p^3-1}{p^3} \right\rfloor = 0.$
ORIGINAL: Need to be more careful about the floor function. With $ 0 \leq a_j \leq p-1, \; \; a_k \neq 0, $ we get $ \left\lfloor \frac{n}{p} \right\rfloor = a_1 + a_2 p + a_3 p^2 + \cdots + a_k p^{k-1}, $ $ \left\lfloor \frac{n}{p^2} \right\rfloor = a_2 + a_3 p + \cdots + a_k p^{k-2}, $ $ \left\lfloor \frac{n}{p^3} \right\rfloor = a_3 + a_4 p + \cdots + a_k p^{k-3}, $ $ \cdots $ $ \left\lfloor \frac{n}{p^{k-1}} \right\rfloor = a_{k-1} + a_k p, $ $ \left\lfloor \frac{n}{p^{k}} \right\rfloor = a_k. $
So, the coefficient of $a_1$ is $1,$ the total coefficient of $a_2$ is $1+p,$ the total coefficient of $a_3$ is $1+p + p^2,$ and so on. What we get is the sum of $ a_j \frac{p^j - 1}{p - 1}. $ Let us look at that a little more. $ v_p (n!) = \sum_{j=0}^k a_j \frac{p^j - 1}{p - 1} = \sum_{j=0}^k a_j \frac{p^j }{p - 1} \; - \; \sum_{j=0}^k a_j \frac{1 }{p - 1}, $ $ v_p (n!) = \sum_{j=0}^k \frac{ a_j p^j }{p - 1} - \sum_{j=0}^k \frac{a_j }{p - 1} = \frac{\sum_{j=0}^k a_j p^j }{p - 1} \; - \; \frac{\sum_{j=0}^k a_j }{p - 1}. $ So, if we name $ S_p(n) = \sum_{j=0}^k a_j, $ we get $ v_p (n!) = \frac{n }{p - 1} \; - \; \frac{ S_p(n) }{p - 1} = \frac{n - S_p(n) }{p - 1}. $
Let's see, $v_p$ means the same as $\mbox{ord}_p.$ The $v$ stands for valuation. The quantity $S_p(n)$ can be called the sum of the digits of $n$ when written in base $p.$ So,
$ v_p (n!) \; \; = \; \; \frac{n - S_p(n) }{p - 1}. $
-
0@anon, I get it now, than$k$s. Than$k$s Will. – 2012-06-08
In the section Counting Prime Factors of n! in Prime Multinomial Divisors, it is shown that
If $n=\sum\limits_{j=0}^ka_jp^j$ and $\sigma_p(n)=\sum\limits_{j=0}^ka_j$ is the sum of the base-$p$ digits of $n$, then $ \mathrm{ord}_p(n!)=\frac{n-\sigma_p(n)}{p-1} $ I think this is the same as the formula you are looking for, but easier on the eye.
Note that $ \begin{align} \left\lfloor\frac{n}{p^m}\right\rfloor &=\left\lfloor\frac{1}{p^m}\sum_{j=0}^ka_jp^j\right\rfloor\\ &=\left\lfloor\sum_{j=m}^ka_jp^{j-m}\;+\;\frac{1}{p^m}\sum_{j=0}^{m-1}a_jp^j\right\rfloor\\ &=\sum_{j=m}^ka_jp^{j-m}+\left\lfloor\frac{1}{p^m}\sum_{j=0}^{m-1}a_jp^j\right\rfloor\\ &=\sum_{j=m}^ka_jp^{j-m} \end{align} $ since $\sum\limits_{j=0}^{m-1}a_jp^j . That is, even if all the $a_j=p-1$, $\sum\limits_{j=0}^{m-1}(p-1)p^j=p^m-1$.