6
$\begingroup$

I try to prove the following formula:

$$n!=\prod_{k=1}^n \operatorname{lcm}(1,2,...,\lfloor n/k \rfloor)$$

I noticed that

$\upsilon_{p}(\operatorname{lcm}(1,2,...,\lfloor n/k \rfloor)) = s$ iff $\lfloor n/(p^{s+1}) \rfloor < k \leq \lfloor n/(p^{s}) \rfloor $

$\endgroup$
5
  • 1
    $\begingroup$ Hint: Use induction along with some properties of greatest integer function . $\endgroup$ Commented Sep 6, 2019 at 10:51
  • 2
    $\begingroup$ @DivyaPrakashSinha I don't think direct induction is helpful here. When you go from $n$ to $n+1$ each term in the product (potentially) changes. $\endgroup$
    – orlp
    Commented Sep 6, 2019 at 10:52
  • 1
    $\begingroup$ It is useful, believe me. $\endgroup$ Commented Sep 6, 2019 at 10:53
  • 1
    $\begingroup$ Induction is useful. Hint: split into cases when $n$ is a prime power or not. oeis.org/A003418 is also useful $\endgroup$ Commented Sep 6, 2019 at 11:00
  • $\begingroup$ See also math.stackexchange.com/questions/2051967 . $\endgroup$ Commented Feb 9, 2021 at 1:18

1 Answer 1

3
$\begingroup$

First, let's notice that the power of $p$ dividing $n!$ is $$ \sum_{i=1}^\infty \left\lfloor \dfrac n{p^i} \right\rfloor \tag{1} \label{1} $$

Secondly, notice that the power of $p$ dividing $\operatorname{lcm}(1,2,...,\ell)$ is the number $q$ which satisfies $p^q \leqslant \ell < p^{q+1}$. So the power of $p$ dividing $\operatorname{lcm}(1,2,...,\lfloor n/k \rfloor)$ is the number $q$ which satisfies the chain of inequalities $p^q \leqslant \lfloor n/k \rfloor < p^{q+1}$. This latter chain of inequalities can be rewritten as $$ \dfrac{n}{p^{q+1}} < k \leqslant \dfrac{n}{p^q} . $$ For any given $q$, the number of all $k \in \left\{1,2,\ldots,n\right\}$ that satisfy this chain of inequalities is $\left\lfloor\dfrac{n}{p^q}\right\rfloor - \left\lfloor\dfrac{n}{p^{q+1}}\right\rfloor$.

So the total power of $p$ dividing $\prod\limits_{k=1}^{n} \operatorname{lcm}(1,2,\ldots,\left\lfloor n/k \right\rfloor)$ is $$ \sum_{q} q\left (\left\lfloor\dfrac{n}{p^q}\right\rfloor - \left\lfloor\dfrac{n}{p^{q+1}}\right\rfloor \right)= \sum_{q} \left\lfloor\dfrac{n}{p^q}\right\rfloor $$ Thus we could find it the same as $\eqref{1}$. And it finished our proof.

$\endgroup$
2
  • $\begingroup$ @orlp do it by summation by parts, and notice that $p$ sums from $1$ to $\infty$ $\endgroup$
    – FFjet
    Commented Sep 6, 2019 at 13:37
  • $\begingroup$ +1, nice solution. I hope my edits improved it. $\endgroup$ Commented Feb 9, 2021 at 1:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .