Proof

(related to Theorem: Number of Multiples of a Prime Number Less Than Factorial)

In the following proof, $p\in\mathbb P$ is a given prime number, $n > 0$ a given natural number and $n !$ its factorial. * First of all, note that the above infinite series $( * )$ is, in fact, convergent, because for all $m$ with $m > \frac{\log n}{\log p}$, ($\log$ beging the natural logarithm), we have: * $p^m > n$ and $0 < \frac n{p^m} < 1.$ * and thus the floor function $\left\lfloor\frac n{p^m}\right\rfloor=0.$ * Therefore, we can write the infinite series as a finite sum: $$\sum_{m=1}^\infty\left\lfloor\frac n{p^m}\right\rfloor=\sum_{1\le m\le \frac{\log n}{\log p}}\left\lfloor\frac n{p^m}\right\rfloor.$$ * Also note that $( * * )$ is correct for $n=1$, since we have $n!=1$ and $( * * )$ is an empty product, which also equals $1.$ * Moreover, if $ p > n$ then there are no multiples $kp$ of $p$ less than $n$ and the sum $( * )$ equals $0$, which in the product $( * * )$ means the factor $1,$ not contributing to the product any more. * So let $n > 1.$ * We can replace the natural number $n$ by the floor function of any positive real number $x > 0$ and get by applying the sum of von Mangoldt function over divisors: $$\log(\lfloor x \rfloor!)=\sum_{n=1}^{\lfloor x \rfloor}\log (n)=\sum_{n=1}^{\lfloor x \rfloor}\sum_{d\mid n}\Lambda(d)=\sum_{d=1}^{\lfloor x \rfloor}\Lambda(d)\left\lfloor \frac xd \right\rfloor.\quad (\dagger) $$ * The last step is because the number of multiples of $d$ with $d\le x$ is given by $\left\lfloor \frac xd \right\rfloor$ and exactly this is the number of $d\le \lfloor x \rfloor,$ for which $\Lambda(d) > 0$ when $d\le n$ and $n$ runs through the numbers $1,2,\ldots,\lfloor x \rfloor.$1 * By the definition of the von Mangoldt function it follows from $(\dagger)$ with the natural logarithm that $$\begin{array}{rcl}\sum_{d=1}^{\lfloor x \rfloor}\Lambda(d)\left\lfloor \frac xd \right\rfloor&=&\sum_{p \le x}\log(p)\left\lfloor \frac xp \right\rfloor+\sum_{p \le x}\log(p)\left\lfloor \frac x{p^2} \right\rfloor+\sum_{p \le x}\log(p)\left\lfloor \frac x{p^3} \right\rfloor+\ldots\\ &=&\sum_{p \le x}\log(p)\sum_{m=1}^\infty\left\lfloor \frac x{p^m} \right\rfloor.\end{array}$$ * Taking the exponential function of this result gives us $$\lfloor x\rfloor!=\prod_{p\in\mathbb P}p^{\sum_{m=1}^\infty\left\lfloor\frac {\lfloor x\rfloor}{p^m}\right\rfloor}$$ * This proves the result $( * * )$ for $x=n.$


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Scheid Harald: "Zahlentheorie", Spektrum Akademischer Verlag, 2003, 3rd Edition
  2. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927

Footnotes


  1. This type of changing the order of two sums is typical for number-theoretic reasoning and a little bit tricky. The reader is invited to try out some simple cases, for instance, $x=2.5$ and $x=4.3$ in this particular case.