6
$\begingroup$

Prove that for all positive integers $ n$ different from $ 3$ and $ 5$, $ n!$ is divisible by the number of its positive divisors.

I tried some things,such as the number of divisors of $ n!$ is just $ \prod_p a_p$ where $ a_p=1+\sum_{j\ge 1}\left\lfloor\frac n{p^j}\right\rfloor\le\min\left(1+\frac n{p-1},n\right)$.

$\endgroup$
  • 3
    $\begingroup$ This question is too easy for MathOverflow (it's suitable for talented high school students, not professional mathematicians). Have you considered posting in StackExchange? See: math.stackexchange.com/questions/ask $\endgroup$ – Vinoth May 24 '18 at 1:40
  • $\begingroup$ @Vinoth,No, I think This problem not easy,it is said from the Erdos,But I can't find it anything with this paper $\endgroup$ – communnites May 24 '18 at 1:45
  • 8
    $\begingroup$ @Vinoth Such claims require substantiation if you don't want to lose your reputation in other people's eyes. So, please show us your solution, Sir. $\endgroup$ – fedja May 24 '18 at 2:17
  • $\begingroup$ @Fedja: Thanks, you might be right..lots of people post easy questions on MathOverflow - based on the description, I thought this post was in that category! $\endgroup$ – Vinoth May 24 '18 at 3:36
  • 4
    $\begingroup$ it is, however, a cross post, math.stackexchange.com/questions/2793196/… $\endgroup$ – Will Jagy May 24 '18 at 16:48
12
$\begingroup$

The sequence, number of divisors of $n$-factorial, is tabulated at the OEIS. It says there that it divides $n!$ for all $n\ge6$, giving a reference to Florian Luca and Paul Thomas Young, On the number of divisors of $n!$ and of the Fibonacci numbers, Glasnik Matematicki, Vol. 47, No. 2 (2012), 285-293, MR3006627. DOI: 10.3336/gm.47.2.05. It gives a link to the article, but my computer couldn't find the site.

This link might work.

$\endgroup$
  • 2
    $\begingroup$ I tabulated this where he first (cross)posted the question on MSE. I also did the same problem with factorial replaced by the LCM of the numbers from $1$ to $N,$ where the thing always fails math.stackexchange.com/questions/2793196/… $\endgroup$ – Will Jagy May 24 '18 at 16:47
3
$\begingroup$

EDIT: here's a better approach; in particular, the formula given in my original answer for $d(n!)$ is completely incorrect as pointed out by Gerhard Paseman.


Divide the primes in $[1,n]$ into the "small primes" $p \le \sqrt{n}$ and the "large primes" $p \ge \sqrt{n}$. Denote by $\pi[a,b]$ the number of primes in the interval $[a,b]$.

For any two small primes $p \neq q$ we have $v_p(n!) \neq v_q(n!)$ - just compare the terms $\lfloor n/p \rfloor$ and $\lfloor n/q \rfloor$. For any large prime $p$ we have $v_p(n!) = \lfloor n/p \rfloor$. In addition, we have $v_p(n!) < n$ for any (small or large) prime $p$.

Now the number of divisors of $n!$ is $\prod_{p \le n\text{ prime}} 1+v_p(n!)$. We split this product into small and large primes.

The product of the small-prime factors is the product of $\pi[1,\sqrt{n}]$ distinct integers between $\sqrt{n}$ and $n$, and hence divides $n!$. In fact, aside from $1+v_2(n!)$, the small-prime factors all lie between $\sqrt{n}$ and $n/2$, and so their product divides $(n/2)!$.

For the large primes a bit more work is needed. We count the number of primes with $\lfloor n/p \rfloor = k$: this is just (up to boundary terms) $\pi\left[\frac{n}{k+1}, \frac{n}{k}\right].$ So the product of the factors for small primes looks something like $$P = 2^{\pi\left[\frac{n}{2},n\right]} \cdot 3^{\pi\left[\frac{n}{3},\frac{n}{2}\right]} \cdot 4^{\pi\left[\frac{n}{4},\frac{n}{3}\right]} \cdots \sqrt{n}^{\pi\left[\sqrt{n},\sqrt{n}+1\right]}.$$

We claim that for large $n$, this product divides $(n/2)!$. We have $$v_2(P) = \pi[n/2,n] + 2\pi[n/4,n/3] + \pi[n/6,n/5] + 3\pi[n/8,n/7] + \cdots.$$ We know that the partial sums of the sequence $\{v_2(2k)\}_{k \ge 1} = \{1, 2, 1, 3, 1, 2, 1, \cdots\}$ are always less than $2k$, so provided $\log n$ is large enough that PNT asymptotics are reasonably valid (e.g., $\pi[n/3, n/2] \ge \pi[n/4, n/3]$) we have $$v_2(P) \le \pi[1,n] \approx \frac{n}{\log n} < v_2((n/3)!) \approx \frac{n}{3}$$ for large enough $n$. An analogous argument gives $v_p(P) \le \pi[1,n/(p-1)]$ which is again eventually less than $v_p((n/3)!)$.

To finish, we note that our total product is at most $(n/2)!(n/3)!\cdot (1+v_2(n!))$. Either $1 + v_2(n!)$ is a prime greater than $n/2$ or it is divisible by $(n/6)!$ for large enough $n$. Finally, we have $(n/2)!(n/3)!(n/6)!$ divides $n!$ by an elementary modular arithmetic argument.

This doesn't give any explicit bound on $n$, but it shows why such a result must be true for large enough $n$. With a fair bit more analytic number theory and cleverness, an explicit bound could presumably be found.


Vinoth is right: this is suitable for talented high school students. Here's a proof sketch.

$d(n)$, the number of divisors, is multiplicative. I'll write $\pi[a,b]$ to denote the number of primes $p$ with $\lfloor a+1 \rfloor \le p \le \lfloor b \rfloor$.

The number of divisors of $n!$ is then $$d(n!) = 2^{\pi[\sqrt{n},n]} \cdot 3^{\pi[\sqrt[3]{n},\sqrt{n}]} \cdot 4^{\pi[\sqrt[4]{n},\sqrt[3]{n}]} \cdots$$

The power of a prime $p$ dividing $n!$ is just $$v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots.$$

So one only needs to establish inequalities of the form

$$\pi[\sqrt{n},n] + 2\pi[\sqrt[4]{n},\sqrt[3]{n}] + \cdots \le \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + \left\lfloor \frac{n}{8} \right\rfloor + \cdots,$$

$$\pi[\sqrt[3]{n},\sqrt{n}] + \pi[\sqrt[6]{n},\sqrt[5]{n}] + 2\pi[\sqrt[9]{n},\sqrt[8]{n}] + \cdots \le \left\lfloor \frac{n}{3} \right\rfloor + \left\lfloor \frac{n}{9} \right\rfloor + \left\lfloor \frac{n}{27} \right\rfloor + \cdots,$$

and so on for primes $p \ge 5$.

If we could establish the following general inequality for $m \le n$, we'd be done:

$$\sum_{k \ge 1} \pi\left[\sqrt[km]{n},\sqrt[km-1]{n}\right] \le \left\lfloor \frac{n}{m} \right\rfloor.$$

The left-hand side is bounded above by $\pi[1,\sqrt[m-1]{n}]$, and the inequality $$\pi[1,\sqrt[m-1]{n}] \le \left\lfloor \frac{n}{m} \right\rfloor$$ is straightforward ($\pi[a,b] \le b - a + 1$) for large $n$ unless $m = 2$. In this case we can use an explicit PNT estimate of the form $\pi[1,n] \le n/C\log n$ for some $1 < C < 2$, or just use an estimate of the form $\pi(n) \le 2 + \frac{n}{3}$, which is true for all $n$ by arithmetic modulo 6.

$\endgroup$
  • 3
    $\begingroup$ No. You need another formula for the number of divisors of n than in your first displayed formula, as the ... does not continue in this fashion. For example, 7! has 2*2*3*5 factors instead of the 2*2*2*3*1 suggested by your display. Gerhard "If It Were That Simple..." Paseman, 2018.05.23. $\endgroup$ – Gerhard Paseman May 24 '18 at 5:13
  • $\begingroup$ Ah, that's correct, and that makes this substantially trickier. Nuts - the proof seemed so straightforward that I didn't think to check the first line! $\endgroup$ – dvitek May 24 '18 at 5:24
  • $\begingroup$ @GerhardPaseman I believe I've fixed the argument. $\endgroup$ – dvitek May 24 '18 at 6:35
  • $\begingroup$ You've fixed part of it. The v2 term has more possibilities than you cover. Gerhard "Still Some Ways To Go" Paseman, 2018.05.23. $\endgroup$ – Gerhard Paseman May 24 '18 at 6:53
  • $\begingroup$ You are almost there. Snow that , except for v2 term, the product of the other terms divides (3n/4)! Gerhard "Is Getting Ready To Exclaim" Paseman, 2018.05.24. $\endgroup$ – Gerhard Paseman May 24 '18 at 7:34
1
$\begingroup$

So there is some challenge in this, but I imagine talented undergraduates can solve it. However, there are some subtleties that I would not expect a very talented high school student to navigate.

As remarked above, the goal is to show that the product of $\pi(n)$ many terms $1+ v_p(n!)$ divides $n!$. Each of these terms is at most $n$, and if they had distinct values, the high school student (and every one else) would be close to done. However, for $p \gt n/2$, these values are $2$, and there are other duplications as well. So we must go further.

As remarked in another post $1+ v_p(n!)$ is bigger than $n/p$. For small primes $p$, we can bound the quantity by $n/(p-1)$ and $n/p$; as long as $p$ is at most $\sqrt{n}$ this guarantees that different $p$ give different values for $1+v_p(n!)$. For larger $p$ though we have the following. If $p \gt 2$ and $q$ is the next larger prime (so $q \geq p+2$) and $k=v_p(n!)=v_q(n!)$ then for some a and b less than $p$ we have $n=kp+a=kq+b\gt kp +2k+b$ giving that $p \gt 2k$ and $2k^2\lt n$, so we get distinct values for primes $p$ below $\sqrt{2n}$. So of the terms $1+v_p(n!)$, one of them is in $[n/2,n]$, one in $[n/3,n/2]$, and the rest are at most $n/4$ and when $p \lt \sqrt{2n}$ are distinct.

The primes $p$ which share a value $k=1+v_p(n!)$ now lie in the interval $I_k=[n/k,n/(k-1))$. If we had the following property (B), that the number of primes in $I_k$ was more than the number of primes in $I_{k+1}$ for enough $k$ ($k$ from 1 to about $\sqrt{n/2}$), then we could finish the problem as follows.

Because of (B), we can collect the repeating values and group them into factorial products, so so many groups form $k!$, so many form $(k-1)!$, all the way down to $2!$. How many? Well, there are $\pi(n)- \pi(n/2)$ many instances of $2$, and about $\pi(n)-\pi(\sqrt{2n})$ terms total, so when we sum up all the largest terms in each group we get $t=2\pi(n) - \pi(n/2) - \pi(\sqrt{2n})$.

Why sum up these largest terms? Because the product of the factorials divides $t!$, as can be seen from multinomial coefficients. If we can get $t $ less than $1+v_3(n!)$, then we have one grouping that divides $(n/2)!$, another (the distinct terms starting with $p=5$) dividing $(n/4)!$, and the term for $p=2$ which is greater than $3n/4$ for large $n$, and the total product then divides $n!$. For small $n$ other verification is needed, but for large $n$ we can get $t$ small enough to make things work.

So given (B), we can have a talented high schooler prove the result. Unfortunately (B) is not always true, and it is not clear if (B) is "true enough" to tweak the argument and finish the proof. We could use some multiples of $1+v_p(n!)$ (even two at a time to use coprimality to an advantage) to get rid of holes and use a (B') assumption, but I am not seeing how weak (B') needs to be, and I am not seeing a nice assignment of more than $O(\sqrt{n})$ values to get around this. Hopefully someone else will see a nice assignment.

Gerhard "Some Assignments Are Rather Hard" Paseman, 2018.05.24.

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