Exercise 4.1.32 ($
u_p(n!) = (n - S(n))/(p-1)$)

Question

Write $n$ in base $p$, and let $S(n)$ denote the sum of the digits in this representation. Show that $p^e \mid \mid n!$ where $a = (n - S(n))/(p-1)$.

Richard Ganaye · Accepted Answer

\begin{proof} 
Let $n = \sum_{j=0}^k a_j p^j$ the writing of $n$ in base $p$, where $0 \leq a_j < p$ for all $j$. Then $S(n) = \sum_{j=0}^k a_j$.

As in the solution of Problem 31, for every $i \in [\![ 0, k]\!]$,
$$n = \left(\sum_{j = i}^k a_j p^{j-i}ight) p^i + \sum_{j = 0}^{i-1} a_j p^j,$$
 where $\sum_{j = 0}^{i-1} a_j p^j \leq \sum_{j = 0}^{i-1} (p-1) p^j  = p^i - 1< p^i$. Therefore
\begin{align}
\left \lfloor \frac{n}{p^i} ight floor &= \sum_{j = i}^k a_j p^{j-i}.
\end{align}
The de Polignac's formula gives
\begin{align*}

u_p(n!) &= \sum_{i = 1}^k \left \lfloor \frac{n}{p^i} ight floor &(	ext{since } \left \lfloor \frac{n}{p^i} ight floor = 0 	ext{ if } i >k)\
&= \sum_{i = 1}^k \sum_{j = i}^k a_j p^{j-i}&(	ext{by equation (1)})\
&=\sum_{j=1}^k \sum_{i=1}^j a_j p^{j-i}\
&= \sum_{j=1}^k a_j(1+p+\cdots + p^{j-1})\
&= \sum_{j=1}^k a_j \, \frac{p^j - 1}{p-1}\
&=\frac{1}{p-1} \left ( \sum_{j = 1}^k a_j p^j - \sum_{j=1}^k a_j ight)\
&=\frac{1}{p-1} \left ( \sum_{j = 0}^k a_j p^j - \sum_{j=0}^k a_j ight) &(	ext{since } a_0 = a_0 p^0)\
&=\frac{n - S(n)}{p-1}.
\end{align*}
We have proved
$$
u_p(n!) = \frac{n - S(n)}{p-1}.$$
\end{proof}

Exercise 4.1.32 ($\nu_p(n!) = (n - S(n))/(p-1)$)

Answers

Comments

Exercise 4.1.32 ($\nu_p(n!) = (n - S(n))/(p-1)$)

Answers

Comments

Add answer