5
$\begingroup$

Let the positive integer $n$ be written as powers of prime $p$ so that we have $n=a_kp^k+....+a_2p^2+a_1p+a_0,$ where $0\leq a_i<p.$ Show that the exponent of the highest power of $p$ appearing in the prime factorization of $n!$ is $\frac{n-(a_k+....+a_1+a_0)}{p-1}$.

I know that the exponent of $p$ in $n!$ is $\sum_{k=1}^{\infty}\left\lfloor\frac{n}{p^k}\right\rfloor$. But I got stuck on how to use the given expression of $n$. Any suggestions?

$\endgroup$
2
$\begingroup$

$$ \begin{align} \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor &= \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dotsb + \left\lfloor \frac{n}{p^k} \right\rfloor + \sum_{i=k+1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor \\ &= \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \dotsb + \left\lfloor \frac{n}{p^k} \right\rfloor \\ &= \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p} \right\rfloor + \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p^2} \right\rfloor + \dotsb \\ &\phantom{= \lfloor} + \left\lfloor \frac{a_kp^k+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\ &= \left\lfloor \frac{n - a_0}{p} + \frac{a_0}{p} \right\rfloor + \left\lfloor \frac{n - (a_1p + a_0)}{p^2} + \frac{a_1p + a_0}{p^2} \right\rfloor + \dotsb \\ &\phantom{= \lfloor} + \left\lfloor \frac{n - (a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0)}{p^k} + \frac{a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\ &= (a_kp^{k-1} + \dotsb + a_2p + a_1) + (a_kp^{k-2} + \dotsb + a_3p + a_2) + \dotsb + (a_k) \\ &\phantom{= \lfloor} + \left\lfloor \frac{a_0}{p} \right\rfloor + \left\lfloor \frac{a_1p + a_0}{p^2} \right\rfloor + \dotsb \left\lfloor \frac{a_{k-1}p^{k-1}+\dotsb+a_2p^2+a_1p+a_0}{p^k} \right\rfloor \\ &= (a_kp^{k-1} + \dotsb + a_2p + a_1) + (a_kp^{k-2} + \dotsb + a_3p + a_2) + \dotsb + (a_k) \\ &= p^{k-1}a_k + p^{k-2}(a_{k-1} + a_k) + \dotsb + p(a_2 + a_3 + \dotsb + a_k) + (a_1 + a_2 + \dotsb + a_k) \\ &= \frac{(p - 1)(p^{k-1}a_k + p^{k-2}(a_{k-1} + a_k) + \dotsb + p(a_2 + a_3 + \dotsb + a_k) + (a_1 + a_2 + \dotsb + a_k))}{p - 1} \\ &= \frac{a_kp^k - a_kp^{k-1} + a_{k-1}p^{k-1} + a_kp^{k-1} - \dotsb + p(a_1 + a_2 + \dotsb + a_k) - (a_1 + a_2 + \dotsb + a_k))}{p - 1} \\ &= \frac{a_kp^k + a_{k-1}p^{k-1} + \dotsb + a_0 - (a_1 + a_2 + \dotsb + a_k)}{p - 1} \\ &= \frac{n - (a_1 + a_2 + \dotsb + a_k)}{p - 1} \end{align} $$

  • Line 2: The remainder of the sum is zero.
  • Line 5: The first part in each floor bracket is an integer, and hence comes outside the brackets.
  • Line 6: The fractions inside the brackets are less than one due to the way $n$ and $a_0, a_1, \dotsc, a_k$ are defined.
  • Line 10: The cancellation works somewhat like a telescopic sum, cancelling all terms except those on the next line. (This can be verified.)
$\endgroup$
  • $\begingroup$ Downvoter, can you please explain? $\endgroup$ – shardulc Dec 23 '15 at 14:40
  • $\begingroup$ You forgot to cancel $a_0$. $\endgroup$ – Yves Daoust Oct 11 '16 at 15:17
0
$\begingroup$

Appying Legendre's formula, the first division yields

$$a_kp^{k-1}+a_{k-1}p^{k-2}+\cdots a_2p+a_1,$$ the next $$a_kp^{k-2}+a_{k-1}p^{k-3}+\cdots a_2,$$ and so on until $$a_k.$$

Summing those terms vertically, we get with the geometric series formula

$$a_k\frac{p^k-1}{p-1}+a_{k-1}\frac{p^{k-1}-1}{p-1}+\cdots a_2\frac{p^2-1}{p-1}+a_1=\frac{a_kp^k+a_{k-1}p^{k-1}+\cdots a_2p^2+a_1p+a_0-a_k-a_{k-1}-\cdots a_1-a_0}{p-1}.$$

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