Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $$ n=a_0+a_1p+\cdots+a_kp^k\qquad 0\leq a_i<p $$ 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.

share|improve this question
    
It's cleaner to do this by induction on $n$. –  Qiaochu Yuan Jun 8 '12 at 3:49
    
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. –  Nastassja Jun 8 '12 at 3:51
    
Think about adding $1$ in base $p$ and looking carefully at carries. –  Qiaochu Yuan Jun 8 '12 at 19:16
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  Nastassja Jun 8 '12 at 4:29
1  
@Nastassja: $a_0+a_1p<p^2$ for the same reason $99<100$, it's built in to how base expansions are defined. –  anon Jun 8 '12 at 4:33
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.$$ –  Will Jagy Jun 8 '12 at 4:34
    
@anon, I get it now, thanks. Thanks Will. –  Nastassja Jun 8 '12 at 4:36
add comment

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<p^m$. That is, even if all the $a_j=p-1$, $\sum\limits_{j=0}^{m-1}(p-1)p^j=p^m-1$.

share|improve this answer
    
Thanks robjohn. –  Nastassja Jun 8 '12 at 4:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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