# If $p^k|n!$ then $p!^k|n!$

Is there a direct proof of the result that if $p$ is a prime and if $p^k|n!$ then $p!^k|n!$? The proof that I know is rather circuitous (take $k$ to be given by de Polignac's formula and construct a subgroup of $S_n$ of order $p!^k$). The result seems too elegant to not admit a slick combinatorial proof.

Induction on $n$: If $n=mp+r$ with $0\le r<p$, there are $\frac{n!}{p!^mr!m!}$ ways to partitoin $n$ objects into $m$ indistinguishable subsets of size $p$ each and a rest of size $r$. Note that $p^{k-m}\mid m!$ (because the multiples of $p$ among $1,2,\ldots, n$ are precisely $p,2p,,\ldots, mp$) and by induction hypothesis $p!^{k-m}\mid m!$. Hence $p!^n\mid p!^mm!\mid n!$.

• I have a little doubt. What if k>m>p. Then the no. dividing $m!$ will be less than $p^{k-m}$ – Lord KK Jun 6 '18 at 6:11
• This looks correct (although I think the $p!^n$ should be $p!^k$ in the last line). It would be nice if there was a non-inductive proof though. – Thomas Browning Jun 6 '18 at 7:04
• I don't follow the reasoning in "because the multiples of $p$ among $1,2,\ldots,n$ are precisely $p,2p,,\ldots,mp$", but there's an alternative way of arguing it: the $p$-adic valuation of $p!^m$ is clearly $m$, and the $p$-adic valuation of $r < p$ is clearly $0$. – Peter Taylor Jun 6 '18 at 10:46
• If you pull out one power of $p$ from each of the $m$ numbers $p,2p,\ldots,mp$, then you get a factor of $p^m$ times the powers of $p$ dividing $1,2,\ldots,m$. This shows that the power of $p$ dividing $(mp+r)!$ is exactly $p^m$ times the power of $p$ dividing $m!$. – Thomas Browning Jun 6 '18 at 16:46

I have not been able to show this in general. But in special case

when $k<p$, which will imply $pk \le n$,

So, the no. of of ways of dividing $n$ objects into $k+1$ different boxes such that $k$ boxes contain $p$ objects, while 1 box contain $n-pk$ object is

$\frac{n!}{(p!)^k\times(n-pk)!}$

From here we get that $(p!)^k|n!$

• Unfortunately, the result only starts to get interesting once $k\geq p$ and extra factors of $p$ start showing up. You can extend this method up to $k<p^2$ if you partition the boxes into blocks of size $p$ and divide out by rearrangement within the blocks. Repeating this construction ends up being equivalent to the group-theoretic proof. – Thomas Browning Jun 6 '18 at 7:08

I was talking to some friends about this problem and we came up with a direct proof that (barely) avoids using de Polignac's formula.

For each factor of $p$ in $n!$, we wish to group that factor of $p$ with something divisible by $(p-1)!$. You group the first factor of $p$ dividing a number $x\in\{1,\ldots,n\}$ with the numbers $x-1,x-2,\ldots,x-(p-1)$. You group the second factor of $p$ dividing a number $px\in\{1,\ldots,n\}$ with the numbers $x-1,x-2,\ldots,x-(p-1)$. These are precisely what is leftover from the numbers $px-p,px-2p,\ldots,px-(p-1)p$ after the first step. Repeating this process, you group the $(k+1)$-st factor of $p$ dividing a number $p^kx\in\{1,\ldots,n\}$ with the numbers $x-1,x-2,\ldots,x-(p-1)$. These are precisely what is leftover from the numbers $p^kx-p^k,p^kx-2p^k,\ldots,p^kx-(p-1)p^k$ after $k$th step. However, the binomial coefficient $$\binom{x-1}{p-1}=(x-1)(x-2)\ldots(x-(p-1))/(p-1)!$$ is an integer. This shows that each group is divisible by $p!$. Also, each factor of $p$ in $n!$ is contained in some group and each group contains exactly one factor of $p$. This shows that if $p^k|n!$ then $p!^k|n!$.

This is still not quite the slick combinatorial proof that I was looking for but it's pretty close.