2
$\begingroup$

Suppose $$ n=a_0+a_1p+\cdots+a_kp^k\qquad 0\leq a_i

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

  • 0
    It's cleaner to do this by induction on $n$.2012-06-08
  • 0
    I thought of trying that, using the fact that $ord_p(n!)=ord_p((n-1)!)+ord_p(n)$, but didn't know how to proceed since the expansions of $n-1$ and $n$ could have different coefficients.2012-06-08
  • 0
    Think about adding $1$ in base $p$ and looking carefully at carries.2012-06-08

2 Answers 2

3

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
    How do you know for instance that $\left\lfloor \frac{n}{p^2} \right\rfloor = a_2 + a_3 p + \cdots + a_k p^{k-2}$? This seems to assume $\left\lfloor\frac{a_0}{p^2}+\frac{a_1}{p}\right\rfloor=0$, and likewise in all the other cases, which is what I felt uneasy about in the first place.2012-06-08
  • 1
    @Nastassja: $a_0+a_1p for the same reason $99<100$, it's built in to how base expansions are defined.2012-06-08
  • 1
    @Nastassja, $$ \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.$$2012-06-08
  • 0
    @anon, I get it now, thanks. Thanks Will.2012-06-08
1

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