Exercise 0.2.8 (Legendre's formula)

Question

Let $p$ be a prime, $n \in \mathbb{Z}^+$. Find a formula for the largest power of $p$ which divides $n! = n(n-1)(n-2)\cdots 2\cdot 1$ (it involves the greatest integer function).

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\ord}{\mathrm{ord}}

\bigskip
I have not discovered this formula, which is known as Legendre's formula, or de Polignac's formula ! I reproduce the proof already given in Ex. 2.6 of Ireland-Rosen (see also  the solution of Ex. 4.1.1 of Niven, Zuckerman, Montgomery).

\bigskip
Here the integer $\ord_p\,  k$ is defined by
$$
u = \ord_p\,  k \iff 
\begin{cases}
p^
u \mid k,\
p^{
u+1} 
mid k.
\end{cases}
$$
\begin{proof} 
The multiples of $q$ in the interval $[\![1 , n]\!]$ are $q,\ 2 q,\ \ldots,\ kq$, where $1 \leq k q \leq n$. Since 
$$1 \leq k q \leq  n \iff 1 \leq k \leq n/q \iff 1 \leq k \leq  \left\lfloor \frac{n}{q}ight floor,$$
 the number of positive multiples $kq$ of $q$ at most equal to $n$ is given by $ \left \lfloor \frac{n}{q}ight floor$.

The number $N_k$ of multiples $m$ of $p^k$ which are not multiple of $p^{k+1}$, where $1\leq m \leq n$, is 
$$N_k = \left \lfloor \frac{n}{p^k}ight floor -\left \lfloor \frac{n}{p^{k+1}}ight floor.$$
Each of these numbers brings the contribution $k$ to the sum $\ord_p\,  n! = \sum\limits_{k=1}^n \ord_p\,  k$.
Thus
\begin{align*}
\ord_p\,  n! &= \sum_{k\geq 1} k \left ( \left \lfloor \frac{n}{p^k}ight floor -\left \lfloor \frac{n}{p^{k+1}}ight floor  ight)\
&=  \sum_{k\geq 1} k  \left \lfloor \frac{n}{p^k}ight floor  - \sum_{k\geq 1}k \left \lfloor \frac{n}{p^{k+1}}ight floor\
&=  \sum_{k\geq 1} k  \left \lfloor \frac{n}{p^k}ight floor  - \sum_{k\geq 2}(k-1) \left \lfloor \frac{n}{p^{k}}ight floor\
&= \left \lfloor \frac{n}{p}ight floor  + \sum_{k\geq 2} \left \lfloor \frac{n}{p^{k}}ight floor\
&= \sum_{k\geq 1} \left \lfloor \frac{n}{p^{k}}ight floor
\end{align*}
So
$$\ord_p\,  n! = \sum_{k\geq 1} \left \lfloor \frac{n}{p^{k}}ight floor.$$

Note that $\left \lfloor \frac{n}{p^{k}}ight floor = 0$ if $p^k >n$, so this sum is finite. Since $p^k > n$ is equivalent to $k >\log(n)/\log(p) = \log_p(n)$, this gives
$$\ord_p\,  n! = \sum_{k= 1}^{\lfloor \log_p(n) floor} \left \lfloor \frac{n}{p^{k}}ight floor.$$

\end{proof}

Exercise 0.2.8 (Legendre's formula)

Answers

Comments

Exercise 0.2.8 (Legendre's formula)

Answers

Comments

Add answer