Let $n \geq 1$ and $n = n_0 + ... n_{\ell}p^{\ell}$ be the p-adic expansion of $n$. Define $\alpha_p(n) = n_0 + ... n_\ell$. Then $\mathrm{ord}_p(n!)= \frac{n - \alpha_p(n)}{p-1}$. I'm trying to prove this by induction and that doesn't seem to work without insanity. Any ideas?
Asked
Active
Viewed 308 times
7
-
2It's not too bad proving it by induction if you make a case distinction, $n \not\equiv -1 \pmod{p}$ - then $\alpha_p(n+1) = \alpha_p(n)+1$, and in the other case, $n = m\cdot p^k - 1$ with $p \not\mid m$. – Daniel Fischer Aug 04 '13 at 18:30
-
How did they discover this formula? Magic? – Daniel Donnelly Aug 04 '13 at 18:31
-
No magic involved. I (re)discovered it myself when I was interested in $v_p(n!)$. Just look at a few cases for small primes, and you'll see the pattern. – Daniel Fischer Aug 04 '13 at 18:33
-
@Daniel: That's technically true, because magic is not witchcraft. ;-) – Asaf Karagila Aug 04 '13 at 18:49
-
1@DanielFischer Or you can apply general induction and show that being true for $\left\lfloor\frac{n}{p}\right\rfloor$ implies it is true for $n$. Essentially, $$\mathrm{ord}_p(n!) = \left\lfloor\frac{n}{p}\right\rfloor + \mathrm{ord}_p\left(\left\lfloor\frac{n}{p}\right\rfloor!\right)$$ and just induct from there. Made easier since $\left\lfloor\frac{n}{p}\right\rfloor = \frac{n-n_0}{p}$. – Thomas Andrews Aug 04 '13 at 19:14
-
He's a magic man momma. – Daniel Donnelly Aug 04 '13 at 19:23
-
Essentially, the induction is on $\ell$, not $n$. – Thomas Andrews Aug 04 '13 at 19:24
-
The von Manglodt function can be used here quite nicely. – Pedro Aug 11 '13 at 23:25
2 Answers
9
You can first note a different formula:
$$\operatorname{ord}_p (n!) = \sum_{i=1}^{\infty} \lfloor n/p^i \rfloor.$$
Now if you write $n= \sum_{i=0}^{\ell} n_i p^i$ you get that the above sum actually only goes up to $\ell$ (then the summands are $0$) and the $j$-th term is $$\sum_{i=j}^{\ell} n_i p^{i-j}.$$
Thus you have expressed what you want as a double sum $$\sum_{j=1}^{\ell} \sum_{i=j}^{\ell} n_i p^{i-j}.$$ Now, rearrange summation, or look with which powers of $p$ each $n_i$ appears. You find $n_i(1 + \dots + p^{i-1})= n_i(p^i -1)/(p-1)$.
So in total you have $$ \sum_{i=1}^{\ell} n_i(p^i -1)/(p-1) = (p-1)^{-1} \sum_{i=0}^{\ell} (n_ip^i -n_i ) = (p-1)^{-1}( n - \sum_{i=0}^{\ell} n_i) $$ as you want.
This leaves to assert the starting representation, but this follows by noting that $\lfloor n/p^1 \rfloor$ is the number of $m\le n$ divisible by $p$, $\lfloor n/p^2 \rfloor$ is the number of $m\le n$ divisible by $p^2$, and so on.
quid
- 42,135
-
1To visualize your starting assertion. I did: floor(n/p) counts the orders of p, floor(n/p^2) adds in the additional orders, and so on... Took some thought but did it in my head. – Daniel Donnelly Aug 04 '13 at 19:21
5
Since $\mathrm{ord}_p(n!)$ is only affected by the numbers divisible by $p$ we see that:
$$\begin{align} \mathrm{ord}_p(n!) &= \mathrm{ord}_p\left((p\cdot 1)(p\cdot 2)\dots \left(p\cdot\left\lfloor\frac{n}{p}\right\rfloor\right)\right) \\&= \left\lfloor\frac{n}{p}\right\rfloor + \mathrm{ord}_p\left(\left\lfloor\frac{n}{p}\right\rfloor!\right) \end{align}$$
So the induction from $n$ to $n+1$ is hard, but the induction from $\left\lfloor\frac{n}{p}\right\rfloor$ to $n$ is relatively easy.
Basically, the induction is on $\ell$, not $n$.
Note that $\left\lfloor\frac{n}{p}\right\rfloor = \frac{n-n_0}p$, and, by the induction hypothesis:
$$\mathrm{ord}_p\left(\left\lfloor\frac{n}{p}\right\rfloor!\right) = \frac{1}{p-1}\left(\frac{n-n_0}{p} - \sum_{i=1}^\ell n_i\right) = \frac{n-n_0}{p(p-1)} - \frac{\sum_{i=1}^\ell n_i}{p-1}$$
Now adding $\frac{n-n_0}{p} = \left\lfloor\frac{n}{p}\right\rfloor$ to both sides and you are done.
Thomas Andrews
- 177,126