Show that $p^{n-1}$ does not divide $k!$, with $p$ an odd prime, $n>1$ and $0<k<n$.

Question

I am trying to prove this claim, which seems true to me, in the process of trying to prove that $p^{n-1}$ divides ${p^{n-1} \choose k}$. Besides the conditions stated in the title, I have already proven that $p^{n-1}$ is strictly larger than $k$.

This has been my final obstacle. It is simple enough with just $p$, but the fact that $p^{n-1}$ is not prime for $n>2$ has made it difficult for me. I'd appreciate any insight.

Answer 1

You need to use the Fundamental Theorem of arithmetic :

Every natural number greater that $1$ can be written as a product of prime numbers in a unique way (up to order).

In particular, when writing $$k!=1\cdot 2\cdots k,$$ if $p^{n-1}|k!$, then the product must contain at least $n-1$ factor $p$.

Now the number of times $p$ appears in $k!$ can be computed by the following formula : $$\left\lfloor \frac{k}{p}\right \rfloor + \left\lfloor \frac{k}{p^2}\right\rfloor +\dots +\left\lfloor \frac{k}{p^{n-2}}\right\rfloor .$$

For a justification of this, see this question (and notice that I can end the sum at $\left\lfloor \frac{k}{p^{n-2}}\right\rfloor$ because $k<p^{n-1}$).

Thus the number of factor $p$ in $k!$ is less than $$\frac{k}{p}+\dots +\frac{k}{p^{n-2}}=\frac{k}{p}\left(1+\dots \frac{1}{p^{n-3}}\right) =\frac{k}{p}\cdot \dfrac{1-\frac{1}{p^{n-2}}}{1-\frac{1}{p}}\leq \frac{k}{p-1}\leq \frac{k}{2}<k\leq n-1.$$

Answer 2

One can try the following approach, which I use to prove the first Sylow theorem: let us write the binomial coefficient as

$$\binom{p^{n-1}}{k}=\frac{p^{n-1}(p^{n-1}-1)\cdot\ldots\cdot\overbrace{(p^{n-1}-(p^{n-1}-k-1))}^{=k+1}}{1\cdot2\cdot3\cdot\ldots\cdots (p^{n-1}-k)}$$

Now, we have

Lemma: for some power $\;0\le r\le n-1\;$ of $\;p\;$ and for all $\;0\le j\le k\;$, we have that $\;p^r\,\mid (p^n-j)\iff p^r\,\mid\,j\;$

Proof: Almost trivial. Try it.

Thus, we get that there's cancelation of $\;p^r\;$ every time this power of $\;p\;$ divides some factor in the numerator...or in the denominator, of course, and thus $\;p^{n-1}\;$ remains uncancelled. The problem's solved once one remembers any binomial coefficient is always an integer.

Answer 3

The highest multiplicity with which $p$ divides $k!$ is (this sum is of course only formally infinite) $$\sum_{j\ge 1} \left\lfloor\frac{k}{p^j} \right\rfloor.$$ To see this note that there are $\lfloor\frac{k}{p} \rfloor$ multiples of $p$ less than or equal to $k$, and $\lfloor\frac{k}{p^2} \rfloor$ multiples of $p^2$ etc. Note that the count is good as multiples of $p$ are counted once, while multiples of $p^2$ are counted twice etc.

Thus you are left with showing that $$\sum_{j\ge 1} \left \lfloor\frac{k}{p^j}\right \rfloor < k$$ Now $\sum_{j\ge 1} \left \lfloor\frac{k}{p^j}\right \rfloor \le \sum_{j\ge 1} \frac{k}{p^j} = k\sum_{j\ge 1} \frac{1}{p^j} = k \frac{1/p}{1-1/p}= k \frac{1}{p-1},$ which is at most $k/2$ for $p$ odd prime, and thus less than $k$.