7
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I have a little doubt. What if k>m>p. Then the no. dividing $m!$ will be less than $p^{k-m}$ $\endgroup$ – Lord KK Jun 6 '18 at 6:11
  • $\begingroup$ 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. $\endgroup$ – Thomas Browning Jun 6 '18 at 7:04
  • $\begingroup$ 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$. $\endgroup$ – Peter Taylor Jun 6 '18 at 10:46
  • 1
    $\begingroup$ 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!$. $\endgroup$ – Thomas Browning Jun 6 '18 at 16:46
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thomas Browning Jun 6 '18 at 7:08
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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